滑县网站建设公司,合肥优化营商环境,搜索引擎优化seo的策略主要有,广州网站建设如何做目录 2019.3.13A.算算算(二项式定理 斯特林数)B.买买买C.树树树2019.3.13比赛链接 A.算算算(二项式定理 斯特林数) 题目链接 \(x^k\)可以用二项式定理展开#xff0c;需要维护的就是\(0\sim k\)次方的\(\sum_{j}F(j,i)\)。加入一个数时#xff0c;每一项都要再用一遍二项式定… 目录 2019.3.13A.算算算(二项式定理 斯特林数)B.买买买C.树树树 2019.3.13 比赛链接 A.算算算(二项式定理 斯特林数) 题目链接 \(x^k\)可以用二项式定理展开需要维护的就是\(0\sim k\)次方的\(\sum_{j}F(j,i)\)。加入一个数时每一项都要再用一遍二项式定理更新复杂度是\(O(nk^2)\)的。 每次加入的数都是一位数考虑如何从\(x^k\)变到\((x1)^k\)。注意到有\(x^k\sum\limits_{i0}^kS(k,i)C(x,i)i!\)\(S\)是第二类斯特林数从\(x\)变成\(x1\)只需维护\(C(x1,i)\)即可然后可以用这个式子\(O(k)\)算出\((x1)^k\)。\(C(x1,i)C(x,i)C(x,i-1)\)所以这个可以\(O(1)\)更新。\(x^k\)变成\((xa)^k\)就重复这个过程\(a\)次即可。\(a^kb^k\sum\limits_{i0}^kS(k,i)\big(C(a,i)C(b,i)\big)i!\)新加入一个数可以直接更新\(C(x,i)\)。 复杂度\(O(Ank)\)\(A\)是所有数位的平均值随机数据下是\(4.5\)。 还有一种容斥做法\(O(nk)\)的太菜了看不懂。\[s_i\sum_{j1}^ia_j\\Ans_i\sum_{j0}^k(-1)^jC_k^js_i^{k-j}\left(\sum_{l0}^{i-1}s_l^j\right)\] 咕咕了 B.买买买 题目链接 看不懂。留坑。然而高考前怕是填不上了... C.树树树 题目链接 貌似是模板题不管了。 转载于:https://www.cnblogs.com/SovietPower/p/10543336.html
