题目
思路
我们首先考虑正常的DP做法，如果不考虑数据范围的话可以考虑状态压缩
我们设\(s_i\)表示i这个数取还是不取
注意是i这个数
再设\(dp_i\)表示以i号节点为根节点的方案总数
转移即为\(dp_i=1+\sum_{i=1}^{k}(s_i*\sum_{j=0}^{k-i}(dp_j*dp_{n-i-j}))\)
我们对\(s_i\)的定义进行考虑，
第i个数取不取？是不是有点熟悉？
这不就是生成函数？
我们记\(F(x)\)为dp的生成函数
我们再记\(A(x)\)为s的生成函数
\(A(x)=\sum_{i=0}^{\infty}(s_i*x^i)\)
\(\begin{aligned}F(x)&=\sum_{n=0}^{\infty}(dp_nx^n)\\&=1+\sum_{n=0}^{\infty}x_n\sum_{i=1}^{k}(s_i*\sum_{j=0}^{k-i}(dp_j*dp_{n-i-j}))\end{aligned}\)
可以发现\(i+j+(n-j-i)=n\)，之后我们观察发现x的角标也是n
所以就可以写成一个卷积的形式
\(F=1+A*F^2\)
\(F^2*(A-1)+1=0\)
大力求根
\(\begin{aligned}F&=\frac{1\pm\sqrt{1-4A}}{2A}&\cdots1\\&=\frac{(1\pm\sqrt{1-4A})*(1\mp\sqrt{1-4A})}{2A*(1\mp\sqrt{1-4A})}\\&=\frac{2}{1\mp\sqrt{1-4A}}&\cdots2\end{aligned}\)
我们先考虑1式，
如果取加号，当\(A(x)\)的\(x\)的取值趋近于无穷小时，也就是\(A\)趋近于无穷小，那么\(F\)就趋近于无穷大，
而我们已知\(F\)是一个多项式，而一个多项式的取值\(x\)的取值趋近于无穷小，函数的值是不可能趋近于无穷大的
即1式只能取负号，即3式取正号
\(\frac{2}{1+\sqrt{1-4A}}\)
代码
#pragma GCC optimize(2)
#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cstdio>
using namespace std;
namespace polynomial
{
const int N=1e5+10;
const int M=N<<3;
const int mod=998244353;
const int G=3;
const int SIZE=sizeof(int);
#define poly vector<int>
int w[M],rev[M];
poly resize(poly f,int n)
{
f.resize(n);
return f;
}
int sub(int a,int b)
{
a-=b;
if(a<0)
return a+mod;
else
return a;
}
int add(int a,int b)
{
a+=b;
if(a>=mod)
return a-mod;
else
return a;
}
int inv(int x)
{
if(x<2)
return 1;
else
return (1ll*mod-mod/x)*inv(mod%x)%mod;
}
int qkpow(int a,int b)
{
if(b==0)
return 1;
if(b==1)
return a;
int t=qkpow(a,b/2);
t=(1ll*t*t)%mod;
if(b%2==1)
t=(1ll*t*a)%mod;
return t;
}
poly operator + (poly f,int a)
{
f[0]=add(f[0],a);
return f;
}
poly operator + (int a,poly f)
{
f[0]=add(f[0],a);
return f;
}
poly operator + (poly f,const poly &g)
{
f.resize(max(f.size(),g.size()));
for(int i=0;i<f.size();i++)
f[i]=add(f[i],i<g.size()?g[i]:0);
return f;
}
poly operator - (poly f,int a)
{
f[0]=sub(f[0],a);
return f;
}
poly operator - (int a,poly f)
{
for(int i=0;i<f.size();i++)
f[i]=sub(0,f[i]);
f[0]=add(f[0],a);
return f;
}
poly operator - (poly f,const poly &g)
{
f.resize(max(f.size(),g.size()));
for(int i=0;i<f.size();i++)
f[i]=sub(f[i],i<g.size()?g[i]:0);
return f;
}
poly operator * (poly f,int a)
{
for(int i=0;i<f.size();i++)
f[i]=1ll*f[i]*a%mod;
return f;
}
poly operator * (int a,poly f)
{
for(int i=0;i<f.size();i++)
f[i]=1ll*f[i]*a%mod;
return f;
}
namespace cipolla_namespace
{
#define x first
#define y second
int t;
int sqrt_w;
pair<int,int> p;
pair<int,int> operator * (const pair<int,int> &a,const pair<int,int> &b)
{
return make_pair((1ll*a.x*b.x+1ll*a.y*b.y%mod*sqrt_w)%mod,(1ll*a.x*b.y+1ll*a.y*b.x)%mod);
}
int cipolla(int x)
{
do
{
t=rand()%mod;
sqrt_w=sub(1ll*t*t%mod,x);
}
while(qkpow(sqrt_w,(mod-1)>>1)!=mod-1);
pair<int,int> s=make_pair(1,0);
pair<int,int> a=make_pair(t,1);
for(int b=(mod+1)>>1;b;b>>=1,a=a*a)
if(b&1)
s=s*a;
return min(s.x,mod-s.x);
}
#undef x
#undef y
}using cipolla_namespace::cipolla;
void ntt(int *a,int lim)
{
for(int i=0;i<lim;i++)
if(i<rev[i])
swap(a[i],a[rev[i]]);
for(int len=1;len<lim;len<<=1)
{
for(int i=0;i<lim;i+=(len<<1))
{
for(int j=0;j<len;j++)
{
int x=a[i+j];
int y=1ll*w[j+len]*a[i+j+len]%mod;
a[i+j]=add(x,y);
a[i+j+len]=sub(x,y);
}
}
}
}
void ntt_init()
{
int wn;
for(int len=1;(len<<1)<M;len<<=1)
{
wn=qkpow(G,(mod-1)/(len<<1));
w[len]=1;
for(int i=1;i<len;i++)
w[i+len]=1ll*w[i+len-1]*wn%mod;
}
}
int init(int len)
{
int lim=1;
int k=0;
while(lim<len)
{
lim<<=1;
k++;
}
for(int i=0;i<lim;i++)
rev[i]=(rev[i>>1]>>1)|((i&1)<<(k-1));
return lim;
}
poly operator * (const poly &f,const poly &g)
{
int a[M]={};
int b[M]={};
int lim=init(f.size()+g.size()-1);
int inv_len=inv(lim);
poly ret;
for(int i=0;i<f.size();i++)
a[i]=f[i];
for(int i=0;i<g.size();i++)
b[i]=g[i];
ntt(a,lim);
ntt(b,lim);
for(int i=0;i<lim;i++)
a[i]=1ll*a[i]*b[i]%mod;
reverse(a+1,a+lim);
ntt(a,lim);
for(int i=0;i<f.size()+g.size()-1;i++)
ret.push_back(1ll*a[i]*inv_len%mod);
return ret;
}
poly inv (const poly &f)//逆元
{
int a[M]={};
int b[M]={};
poly g;
g.push_back(inv(f[0]));
for(int len=2;(len>>1)<f.size();len<<=1)
{
int lim=init(len<<1);
int inv_len=inv(lim);
memset(&a[len],0,len*SIZE);
memset(&b[len],0,len*SIZE);
for(int i=0;i<len;i++)
a[i]=i<f.size()?f[i]:0;
for(int i=0;i<len;i++)
b[i]=i<g.size()?g[i]:0;
ntt(a,lim);
ntt(b,lim);
for(int i=0;i<lim;i++)
a[i]=(1ll*a[i]*b[i]%mod)*b[i]%mod;
reverse(a+1,a+lim);
ntt(a,lim);
g.resize(len);
for(int i=0;i<g.size();i++)
g[i]=sub(add(g[i],g[i]),1ll*a[i]*inv_len%mod);
g.resize(f.size());
}
g.resize(f.size());
return g;
}
poly sqrt(const poly &f)//开根
{
poly g;
g.push_back(cipolla(f[0]));
for(int len=2;(len>>1)<f.size();len<<=1)
g=resize(resize(resize(g*g,len)+f,len)*inv(resize(2*g,len)),len);
g.resize(f.size());
return g;
}
poly deri(const poly &f)//求导
{
poly g;
for(int i=0;i<f.size()-1;i++)
g.push_back(1ll*(i+1)*f[i+1]%mod);
g.push_back(0);
return g;
}
poly inte(poly f)//积分
{
poly g;
g.push_back(0);
for(int i=0;i<f.size()-1;i++)
g.push_back(1ll*inv(i+1)*f[i]%mod);
return g;
}
poly ln(const poly &f)
{
return inte(resize(deri(f)*inv(f),f.size()));
}
poly exp(const poly &f)
{
poly g;
g.push_back(1);
for(int len=2;(len>>1)<f.size();len<<=1)
g=resize(g*(1-ln(resize(g,len))+resize(f,len)),len);
g.resize(f.size());
return g;
}
void div (poly f,poly q,poly &g,poly &r)
{
int lenq=q.size();
reverse(f.begin(),f.end());
reverse(q.begin(),q.end());
poly _q=q;
q=resize(q,f.size()-q.size()+1);
g=resize(f*inv(q),f.size()-lenq+1);
reverse(g.begin(),g.end());
reverse(f.begin(),f.end());
q=_q;
reverse(q.begin(),q.end());
r=resize(f-q*g,lenq-1);
}
poly qkpow(poly a,int b)
{
int n=a.size();
poly s;
s.push_back(1);
while(b)
{
if(b&1)
s=resize(s*a,n);
a=resize(a*a,n);
b>>=1;
}
return s;
}
#undef poly
};
using namespace polynomial;
void read(int &x)
{
x=0;
int f=1;
char c=getchar();
while('0'>c||c>'9')
{
if(c=='-')
f=-1;
c=getchar();
}
while('0'<=c&&c<='9')
{
x=(x<<3)+(x<<1)+c-'0';
c=getchar();
}
x*=f;
}
void write(int x)
{
if(x>9)
write(x/10);
putchar(x%10+'0');
}
int n,m;
vector<int> g;
vector<int> f;
int main()
{
ntt_init();
cin>>n>>m;
m++;
g.resize(m);
for(int i=1;i<=n;i++)
{
int x;
cin>>x;
if(x<m)
g[x]=1;
}
g=1-4*g;
g.resize(m);
g=1+sqrt(g);
g.resize(m);
f=2*inv(g);
f.resize(m);
for(int i=1;i<m;i++)
cout<<f[i]<<'\n';
return 0;
}