用多项式的逆优化dp总结
思量一个经典的模子：
d p i = ∑ j = 1 i d p i − j × f j dp_i=\sum_{j=1}^i dp_{i-j}\times f_j dpi=∑j=1idpi−j×fj
求 d p n dp_n dpn 这种问题外貌看上去需要 n 2 n^2 n2，但是事实上可以更优。
我们创建一个长度无穷大的多项式: F ( x ) = ∑ i = 0 ∞ f i × x i F(x)=\sum _{i=0}^\infty f_{i}\times x^i F(x)=∑i=0∞fi×xi,特殊的： f 0 = f k + n = 0 , k ∈ N ∗ f_{0}=f_{k+n}=0,k\in \mathbb{N}^* f0=fk+n=0,k∈N∗
然后可以发现 d p n = ∑ i = 0 ∞ [ x n ] ( F i ( x ) ) dp_n=\sum _{i=0}^{\infty}[x^n](F^i(x)) dpn=∑i=0∞[xn](Fi(x))
由于 ∑ i = 0 ∞ x i = 1 1 − x \sum _{i=0}^{\infty} x^i=\frac{1}{1-x} ∑i=0∞xi=1−x1
所以: d p n = [ x n ] 1 1 − F ( x ) dp_{n}=[x^n]\frac{1}{1-F(x)} dpn=[xn]1−F(x)1
然后 d p n dp_n dpn就是多项式 G ( x ) = 1 − F ( x ) G(x)=1-F(x) G(x)=1−F(x)的逆的第n项系数。
如何求多项式的逆元？
题解 P4238 【模板】多项式求逆- Great_Influence 的博客 - 洛谷博客 (luogu.com.cn)
my code:
[code]const int MOD=998244353;const int g=3;int len;int rev[11]>>1; if(i&1) rev|=len>>1; } rep(i,len) if(rev>i) swap(v,v[rev]);}LL quick(LL A,LL B){ if(B==0) return 1; LL tmp=quick(A,B>>1); tmp*=tmp; tmp%=MOD; if(B&1) tmp*=A,tmp%=MOD; return tmp;}int inv(int x){ return quick(x,MOD-2);}vector ntt(vector v,int ty){ butterfly(v); vector nex; for(int l=2;l |
