题解 P4721 【【模板】分治 FFT】
a2956331800
2019-01-05 21:49:15
生成函数
$$f[i]=\sum_{j=1}^if[i-j]*g[j],i>0$$
设$f(x)=\sum\limits_{i=0}^\infty f[i]x^i,g(x)=\sum\limits_{i=0}^\infty g[i]x^i$(设$g[0]=0$)
发现把$f$和$g$卷积后$f$**常数项**没有了:
$$f(x)*g(x)=\sum_{i=0}^\infty\sum_{j=0}^\infty f[i]\times g[j]x^{i+j}$$
令$k=i+j$
$$f(x)*g(x)=\sum_{k=0}^\infty(\sum_{j=0}^kf[k-j]g[j])x^k$$
$k>0$时$\sum_{j=0}^kf[k-j]g[j]=f[k]$
$k=0$时$\sum_{j=0}^kf[k-j]g[j]=0$($g[0]=0$)
所以$f(x)*g(x)=\sum\limits_{k=1}^\infty f[k]x^k$,和$f(x)$对比一下发现就差了一个常数项
即$f(x)*g(x)+f[0]=f(x)$
然后用初中数学知识(就是把未知数换成了多项式)就能算出来
$$f(x)=\frac{f[0]}{1-g(x)}$$
多项式求逆就完了
~~生成函数真是人类智慧做法~~
代码(是个~~正在完善的~~多项式板子,什么$\ln \exp$都有可以拿去看)
```cpp
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define md 998244353LL
#define inv(x) power(x,md-2)
#define max_n 1000000
using namespace std;
int n,N,i;
long long num[max_n],ans[max_n];
//const double pi=acos(-1);
//
//struct complex
//{
// double x,y;
// complex operator +(complex a)
// {
// return (complex){x+a.x,y+a.y};
// }
// complex operator -(complex a)
// {
// return (complex){x-a.x,y-a.y};
// }
// complex operator *(complex a)
// {
// return (complex){x*a.x-y*a.y,x*a.y+y*a.x};
// }
// complex operator /(double a)
// {
// return (complex){x/a,y/a};
// }
//};
long long power(long long a,long long n)
{
long long ans=1;
while(n)
{
if(n&1)
ans=ans*a%md;
a=a*a%md;
n>>=1;
}
return ans;
}
int re[max_n];
void build_re(int N)
{
int x,now=N>>1,len=0;
while(now)
len++,now>>=1;
for(int i=0;i<N;i++)
{
x=i;now=0;
for(int j=0;j<len;j++)
now=(now<<1)|(x&1),x>>=1;
re[i]=now;
}
}
//void FFT(complex a[],int len,int opt)
//{
// for(int i=0;i<len;i++)
// if(i<re[i])
// swap(a[i],a[re[i]]);
// complex wn,w,x;
// for(int i=2;i<=len;i<<=1)
// for(int j=(wn=(complex){cos(pi*2/i),opt*sin(pi*2/i)},0);j<len;j+=i)
// for(int k=(w=(complex){1,0},0);k<i>>1;k++,w=w*wn)
// x=w*a[j+k+(i>>1)],a[j+k+(i>>1)]=a[j+k]-x,a[j+k]=a[j+k]+x;
// if(opt==-1)
// for(int i=0;i<len;i++)
// a[i]=a[i]/len;
//}
void NTT(long long a[],int len,int opt)
{
for(int i=0;i<len;i++)
if(i<re[i])
swap(a[i],a[re[i]]);
long long wn,w,x;
for(int i=2;i<=len;i<<=1)
for(int j=(wn=power(3,(md-1)/i),(opt==-1?wn=power(wn,md-2):0),0);j<len;j+=i)
for(int k=(w=1,0);k<i>>1;k++,w=w*wn%md)
x=a[j+k+(i>>1)]*w%md,a[j+k+(i>>1)]=(a[j+k]-x+md)%md,a[j+k]=(a[j+k]+x)%md;
if(opt==-1)
{
long long inv=power(len,md-2);
for(int i=0;i<len;i++)
a[i]=a[i]*inv%md;
}
}
//void poly_mul(long long a[],long long b[],long long tar[],int len)
//{
// static long long A[4*max_n],B[4*max_n];
// memcpy(A,a,sizeof(long long)*len);memcpy(B,b,sizeof(long long)*len);
// build_re(len);
// NTT(A,len,1);NTT(B,len,1);
// for(int i=0;i<len;i++)
// tar[i]=A[i]*B[i]%md;
// NTT(tar,len,-1);
//}
void poly_inv(long long a[],long long tar[],int len)
{
static long long now[4*max_n],ret[4*max_n];
memset(now,0,sizeof(long long)*len);memset(ret,0,sizeof(long long)*len);
ret[0]=inv(a[0]);
for(int i=2;i<=len;i<<=1)
{
build_re(i<<1);
memcpy(now,a,sizeof(long long)*i);
NTT(ret,i<<1,1);NTT(now,i<<1,1);
for(int j=0;j<i<<1;j++)
ret[j]=ret[j]*(2LL-now[j]*ret[j]%md+md)%md;
NTT(ret,i<<1,-1);
memset(ret+i,0,sizeof(long long)*i);
}
memcpy(tar,ret,sizeof(long long)*len);
}
//void poly_dir(long long a[],long long tar[],int len)
//{
// for(int i=0;i<len-1;i++)
// tar[i]=a[i+1]*(i+1)%md;
//}
//void poly_int(long long a[],long long tar[],int len)
//{
// for(int i=len;i>=1;i--)
// tar[i]=a[i-1]*inv(i)%md;
// tar[0]=0;
//}
//void poly_ln(long long a[],long long tar[],int len)
//{
// static long long now[4*max_n],ret[4*max_n];
// memset(now,0,sizeof(long long)*len);memset(ret,0,sizeof(long long)*len);
// poly_inv(a,ret,len);
// poly_dir(a,now,len);
// poly_mul(now,ret,ret,len<<1);
// poly_int(ret,ret,len);
// memcpy(tar,ret,sizeof(long long)*len);
//}
//void poly_exp(long long a[],long long tar[],int len)
//{
// static long long now[4*max_n],ret[4*max_n],ln[4*max_n];
// memset(now,0,sizeof(long long)*len);memset(ret,0,sizeof(long long)*len);memset(ln,0,sizeof(long long)*len);
// ret[0]=1;
// for(int i=2;i<=len;i<<=1)
// {
// poly_ln(ret,now,i);
// for(int j=0;j<i;j++)
// now[j]=(a[j]-now[j]+(j==0)+md)%md;
// poly_mul(now,ret,ret,i<<1);
// }
// memcpy(tar,ret,sizeof(long long)*len);
//}
char Getchar()
{
return getchar();
static char buff[1000000],*p,*end=p;
if(p==end)
end=buff+fread(p=buff,1,1000000,stdin);
return *(p++);
}
template<typename T>void read(T &x)
{
static char rc;
x=0;rc=Getchar();
while(!isdigit(rc))
rc=Getchar();
while(isdigit(rc))
x=x*10+rc-'0',rc=Getchar();
}
int main()
{
read(n);num[0]=1;
for(i=1;i<n;i++)
read(num[i]),num[i]=-num[i];
N=1;
while(N<n)
N<<=1;
poly_inv(num,ans,N);
for(i=0;i<n;i++)
cout<<ans[i]<<' ';
return 0;
}
```