题解 P4721 【【模板】分治 FFT】

多项式求逆大法好! ________________ 如果你不会生成函数那一套理论请左转问度娘 我们考虑万能的生成函数……来求这个多项式f 假设这个多项式的生成函数是$f(x)$那么我们就是要求这个多项式的生成函数 然后我们呢发现这个生成函数$f(x)$有一个非常棒的特点，就是它卷积一个$g(x)$之后整体向右移了一位 所以我们可以列出这样一个多项式方程 ## $f(x)g(x)+f_{0}=f(x)$ 然后移项 ## $(1-g(x))f(x)=f_{0}$ 由于我们只需要求出$f(x)$的前n项，所以我们可以在膜$x^{n}$的意义下进行运算 ## $(1-g(x))f(x) \equiv f_{0} (modx^n)$ 此时我们就可以两边同时乘逆元啦…… ## $f(x) \equiv f_{0}(1-g(x))^{-1} (mod x^n)$ 剩下的事情就是左转隔壁“【模板】 多项式求逆”然后粘一遍板子的事情啦…… 上代码~ ```C #include<cstdio> #include<algorithm> using namespace std;const int N=262144+10;typedef unsigned long long ll;const ll mod=998244353; int rv[N];ll rt[2][20];ll tr1[N];ll tr2[N];ll g[N];ll ig[N];int Len;int n; inline ll po(ll a,ll p){ll r=1;for(;p;p>>=1,a=a*a%mod)if(p&1)r=r*a%mod;return r;} inline void ntt(ll* a,int o,int len)//ntt { for(int i=0;i<len;i++)if(i<rv[i])swap(a[i],a[rv[i]]);ll a0,a1; for(int k=1,j=1;k<len;k<<=1,j++) for(int s=0;s<len;s+=(k<<1)) for(int i=s,w=1;i<s+k;i++,w=w*rt[o][j]%mod) a0=a[i],a1=w*a[i+k]%mod,a[i]=(a0+a1)%mod,a[i+k]=(a0+mod-a1)%mod; if(o==1){ll inv=po(len,mod-2);for(int i=0;i<len;i++)(a[i]*=inv)%=mod;} } inline void poly_inv(ll* a,ll* b,int len)//倍增多项式求逆 { b[0]=po(a[0],mod-2); for(int k=1,j=0;k<=len;k<<=1,j++) { for(int i=1;i<(k<<1);i++)rv[i]=(rv[i>>1]>>1)|((i&1)<<j); for(int i=0;i<k;i++)tr1[i]=a[i];for(int i=0;i<k;i++)tr2[i]=b[i]; ntt(tr1,0,k<<1);ntt(tr2,0,k<<1); for(int i=0;i<(k<<1);i++)b[i]=tr2[i]*(2+mod-tr1[i]*tr2[i]%mod)%mod; ntt(b,1,k<<1);for(int i=k;i<(k<<1);i++)b[i]=0; } } int main() { for(int k=2,j=1;j<=18;k<<=1,j++)rt[0][j]=po(3,(mod-1)/k); for(int k=2,j=1;j<=18;k<<=1,j++)rt[1][j]=po(332748118,(mod-1)/k); scanf("%d",&n);for(int i=1;i<n;i++)scanf("%lld",&g[i]); for(Len=1;Len<n;Len<<=1);for(int i=1;i<n;i++)g[i]=mod-g[i];(g[0]+=1)%=mod;//处理出要求逆的多项式 poly_inv(g,ig,Len); for(int i=0;i<n;i++)printf("%lld ",ig[i]);printf("\n");return 0; } ```