2019.3.13

比赛链接

A.算算算(二项式定理 斯特林数)

题目链接

\(x^k\)可以用二项式定理展开,需要维护的就是\(0\sim k\)次方的\(\sum_{j}F(j,i)\)。加入一个数时,每一项都要再用一遍二项式定理更新,复杂度是\(O(nk^2)\)的。

每次加入的数都是一位数,考虑如何从\(x^k\)变到\((x+1)^k\)。注意到有\(x^k=\sum\limits_{i=0}^kS(k,i)C(x,i)i!\)(\(S\)是第二类斯特林数),从\(x\)变成\(x+1\)只需维护\(C(x+1,i)\)即可(然后可以用这个式子\(O(k)\)算出\((x+1)^k\))。

\(C(x+1,i)=C(x,i)+C(x,i-1)\),所以这个可以\(O(1)\)更新。

\(x^k\)变成\((x+a)^k\)就重复这个过程\(a\)次即可。

\(a^k+b^k=\sum\limits_{i=0}^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_{j=1}^ia_j\\Ans_i=\sum_{j=0}^k(-1)^jC_k^js_i^{k-j}\left(\sum_{l=0}^{i-1}s_l^j\right)
\]


咕咕了

B.买买买

题目链接

看不懂。留坑。(然而高考前怕是填不上了...)




C.树树树

题目链接

貌似是模板题,不管了。




05-23 19:51