玩游戏

这应该是省选前我写的最后一道多项式(模拟赛除外

玩游戏

传送门

对于每个$t$求$\sum\limits_{i=1}^n\sum\limits_{j=1}^m\sum\limits_{k=0}^t\binom{t}{k}a_i^kb_j^{t-k}$

这个东西直接卷积就好了,考虑$s$怎么求

设$f(x)=\sum\limits_{k=0}^{\infty}\sum\limits_{i=1}^na_i^kx^k​$

显然,$s_k$为$f(x)$的第$k$项系数

实际上到这步就可以了,这个$f(x)$可以直接分治$NTT$求

但是上面那个柿子常数巨大。。。如果你的$NTT$不够优美,你就$GG$了(这里有一个我的板子,大概可以过吧)

一个常数较小的解法

然后$g$就可以分治$NTT$了,然后考虑怎么求$f$,先给结论

证明考虑还原生成函数

$g$对于每个$a$的数列为$-a,-a^2x,-a^3x^2,-a^4x^3…$

然后发现$f$是$1,ax,a^2x^2,a^3x^3…$

相当于把$g$右移一位然后补上$0$次项

莫得代码

avatar
ZJOI2018历史

  1. 1. 玩游戏
    1. 1.1. 一个常数较小的解法
    2. 1.2. 莫得代码