hdu5322 Hope(dp+FFT+分治)
题目大意：n个数的排列，每个数向后面第一个大于它的点连边，排列的权值为每个联通块大小的平方，求所有排列的权值和。
思路：
考虑直接设dp[i]表示n=i时的答案。
我们考虑放完前n-1个数之后再插入n，会发现n前面所有数都和它联通。
于是dp方程就出来了：
$dp[n]=Sigma(dp[n-k]*k^{2}*(k-1)!*C_{n-1}^{k-1})$
组合数倒腾过来变成：
$frac{dp[n]}{(n-1)!}=Sigma(frac{dp[n-k]}{(n-k)!}*k^{2})$
分治FFT搞定。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 typedef long long lint; 6 const lint mo=998244353; 7 const int N=600069; 8 lint fpow(lint a,lint p) 9 { 10 lint ret=1; 11 while(p) 12 { 13 if(p&1ll) (ret*=a)%=mo; 14 (a*=a)%=mo; 15 p>>=1; 16 } 17 return ret; 18 } 19 lint fac[N],ifac[N],i2[N]; 20 lint dp[N]; 21 22 int inv[N]; 23 lint wg[N],iwg[N]; 24 void ntt(lint *a,int len,int tp) 25 { 26 lint ilen=fpow(len,mo-2); 27 for(int i=0;i<len;i++) if(i<inv[i]) swap(a[i],a[inv[i]]); 28 for(int i=1;i<len;i<<=1) 29 { 30 lint w0=(~tp)?wg[i]:iwg[i]; 31 for(int j=0;j<len;j+=(i<<1)) 32 { 33 lint w=1; 34 for(int k=0;k<i;k++,(w*=w0)%=mo) 35 { 36 lint w1=a[j+k],w2=w*a[j+k+i]%mo; 37 a[j+k]=(w1+w2)%mo,a[j+k+i]=(w1-w2+mo)%mo; 38 } 39 } 40 } 41 if(tp==-1) for(int i=0;i<len;i++) (a[i]*=ilen)%=mo; 42 } 43 lint a[N],b[N],c[N]; 44 void cdq(int l,int r) 45 { 46 if(l==r) {(dp[l]*=(l?fac[l-1]:1))%=mo;return;} 47 int mm=l+r>>1; 48 cdq(l,mm); 49 int len=1,pl=0,n=r-l+1; 50 while(len<=n) len<<=1,pl++; 51 for(int i=1;i<len;i++) inv[i]=(inv[i>>1]>>1)|((i&1)<<(pl-1)); 52 for(int i=0;i<len;i++) a[i]=b[i]=0; 53 for(int i=0;i<mm-l+1;i++) a[i]=dp[i+l]*ifac[i+l]%mo; 54 for(int i=0;i<r-l+1;i++) b[i]=i2[i]; 55 ntt(a,len,1),ntt(b,len,1); 56 for(int i=0;i<len;i++) c[i]=a[i]*b[i]%mo; 57 ntt(c,len,-1); 58 for(int i=mm+1;i<=r;i++) (dp[i]+=c[i-l])%=mo; 59 cdq(mm+1,r); 60 } 61 62 63 int xi,T; 64 int main() 65 { 66 fac[0]=ifac[0]=1; 67 for(int i=1;i<=100000;i++) fac[i]=fac[i-1]*i%mo,ifac[i]=fpow(fac[i],mo-2),i2[i]=1ll*i*i%mo; 68 for(int i=1;i<524288;i<<=1) wg[i]=fpow(3,(mo-1)/(i<<1)),iwg[i]=fpow(wg[i],mo-2); 69 dp[0]=1; 70 cdq(0,100000); 71 while(scanf("%d",&xi)!=EOF) printf("%lld ",dp[xi]); 72 return 0; 73 }