比賽鏈接
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.樹樹樹
題目鏈接
貌似是模板題，不管了。
腳本滲透實戰)
