本文共 1844 字，大约阅读时间需要 6 分钟。
生成函数又有奇妙的性质。
$F(x)=C(x)*F(x)*F(x)+1$
然后大力解方程，得到一个带根号的式子。
多项式开根有解只与常数项有关。
发现两个解只有一个是成立的。
然后多项式开根、求逆。
不太会算复杂度为什么是$n\log {n}$的。
开根号里套了一个求逆，不应该是两个$\log$？
#include #include #include #include #include #include #include using namespace std;#define F(i,j,k) for (int i=j;i<=k;++i)#define D(i,j,k) for (int i=j;i>=k;--i)#define ll long long#define mp make_pair#define md 998244353#define maxn 500005#define g 3 int rev[maxn],n,m,C[maxn],N,l,x,Root_C[maxn],Inv_Root_C[maxn],Inv2; int ksm(int a,int b){ int ret=1; for (;b;b>>=1,a=(ll)a*a%md) if (b&1) ret=(ll)ret*a%md; return ret;} void NTT(int *x,int n,int flag){ F(i,0,n-1) if (rev[i]>i) swap(x[i],x[rev[i]]); for (int m=2;m<=n;m<<=1) { int wn=ksm(g,((md-1)/m*flag+md-1)%(md-1)); for (int i=0;i >1);++j) { int u=x[i+j],v=(ll)x[i+j+(m>>1)]*w%md; x[i+j]=(u+v)%md,x[i+j+(m>>1)]=(u-v+md)%md; w=(ll)w*wn%md; } } } if (flag==-1){int inv=ksm(n,md-2);F(i,0,n-1)x[i]=(ll)x[i]*inv%md;}}void Get_Inv(int *a,int *b,int n){ static int tmp[maxn]; if (n==1) {b[0]=ksm(a[0],md-2);return;} Get_Inv(a,b,n>>1); F(i,0,n-1) tmp[i]=a[i],tmp[n+i]=0; int L=0;while(!(n>>L&1))L++; F(i,0,(n<<1)-1) rev[i]=(rev[i>>1]>>1)|((i&1)< >1); F(i,0,n-1) b_Inv[i]=0; Get_Inv(b,b_Inv,n); F(i,0,n-1) tmp[i]=a[i],tmp[i+n]=0; NTT(tmp,n<<1,1);NTT(b,n<<1,1);NTT(b_Inv,n<<1,1); F(i,0,(n<<1)-1) tmp[i]=(ll)Inv2*(b[i]+(ll)b_Inv[i]*tmp[i]%md)%md; NTT(tmp,n<<1,-1);F(i,0,n-1) b[i]=tmp[i],b[n+i]=0;} int main(){ scanf("%d%d",&n,&m);Inv2=ksm(2,md-2); F(i,1,n)scanf("%d",&x),C[x]=(C[x]-4+md)%md; C[0]=1;for(N=1;N<=m;N<<=1); Get_Root(C,Root_C,N); Root_C[0]=(1+Root_C[0])%md; Get_Inv(Root_C,Inv_Root_C,N); F(i,0,100000) Inv_Root_C[i]=(ll)2*Inv_Root_C[i]%md; F(i,1,m) printf("%d\n",Inv_Root_C[i]);}
转载于:https://www.cnblogs.com/SfailSth/p/6776419.html