第一眼:这不是无穷级数吗怎么算啊……
看题解:壮哉我大生成函数!
考虑把多项式拆成若干单项式计算,即设 fk=∞∑n=0nkrn
则答案即 m∑i=0aifi。
推一推式子: fk=∞∑n=0(n+1)krn+1rfk=∞∑n=0nkrn+1(1−r)fk=r∞∑n=0[(n+1)k−nk]rn=r∞∑n=0rnk−1∑i=0(ki)ni=rk−1∑i=0(ki)∞∑n=0nirn=rk−1∑i=0(ki)fifk=r1−rk−1∑i=0(ki)fi
熟悉的 EGF 卷积,于是设 F 为 f 的 EGF,则有 F(x)=r1−rF(x)(ex−1)+1[1−r1−r(ex−1)]F(x)=1F(x)=11−rex
多项式求逆!
代码:
1 |
|