【xsy1301】原题的价值组合数+斯特林数+FFT

题目大意：求$n\times2^{\frac{(n-1)(n-2)/2}{2}}\sum\limits_{i=0}^{n-1}\dbinom{n-1}{i}i^k$

数据范围：$n≤10^9$，$k≤10^5$，答案对$998244353$取模。

我们令$F(n,k)=\sum\limits_{i=0}^{n-1}\binom{n-1}{i}i^k$。

那么最终要输出的东西显然就是$n\times2^{\frac{(n-1)(n-2)/2}{2}}F(n,k)$

我们令$G(n,k)=(n-1)^\underline{k}2^{n-1-k}$

我们先考虑下当$k=0$的时候要怎么做，我们显然有：

$F(n,0)=\sum\limits_{i=0}^{n-1}\binom{n-1}{i}=2^{n-1}$

化简是根据二项式定理来的，在此不展开说了。

考虑下当$k=1$的时候要怎么做：

$F(n,1)=\sum\limits_{i=0}^{n-1}\dbinom{n-1}{i}i
\\
=\sum\limits_{i=0}^{n-1}\dfrac{(n-1)!}{i!(n-1-i)!}i
\\
=\sum\limits_{i=1}^{n-1}\dfrac{(n-1)!}{(i-1)!(n-1-i)!}
\\
=\sum\limits_{i=1}^{n-1}\dfrac{(n-1)!}{(i-1)!((n-2)-(i-1))!}
\\
=(n-1)\sum\limits_{i=1}^{n-1}\dfrac{(n-2)!}{(i-1)!((n-2)-(i-1))!}
\\
=（n-1)\sum\limits_{i=1}^{n-1}\dbinom{n-2}{i-1}
\\
=(n-1)F(n-1,0)=G(n,1)$

我们考虑按照$k=1$的化简方法来化简$k=2$，由于跟上文比较相似，所以可能会有不少的跳步

$F(n,2)=\sum\limits_{i=0}^{n-1}\dbinom{n-1}{i}i^2$

$=\sum\limits_{i=0}^{n-1}\dfrac{(n-1)!}{i!(n-1-i)!}i^2$

$=(n-1)\sum\limits_{i=1}^{n-1}\dbinom{n-2}{i-1}i$

$=(n-1)\sum\limits_{i=1}^{n-1}\dfrac{(n-2)!}{(i-1)!\big((n-2)-(i-1)\big)!}\big((i-1)+1\big)$

$=F(n-1,1)+(n-1)\sum\limits_{i=1}^{n-1}\dfrac{(n-2)!}{(i-2)!\big((n-3)-(i-2)\big)!}$

$=F(n-1,1)+(n-1)(n-2)\sum\limits_{i=1}^{n-1}\dfrac{(n-3)!}{(i-2)!\big((n-3)-(i-2)\big)!}$

$=F(n-1,1)+(n-1)(n-2)F(n-2,0)$

$=G(n,1)+G(n,2)$

根据k=2的推法，我们推出了$k=3$和$k=4$的情况：

$F(n,3)=G(n,1)+3G(n,2)+4G(n,3)$

$F(n,4)=G(n,1)+7G(n,2)+6G(n,3)+G(n,4)$

诶？这不是斯特林三角形吗（证明显然，这里不证了）

于是有：

$F(n,m)=\sum\limits_{i=1}^{m}S2(n,i)G(n,i)$

$G(n,1\cdots k)$可以在$O(k)$的时间复杂度内求出来，$S2(n,1\cdots k)$可以在$O(k\log\ k)$的复杂度内用FFT求出来。

完结撒花~

 #include<bits/stdc++.h>

 #define MOD 998244353

 #define L long long

 #define M (1<<18)

 #define G 3

 using namespace std;

 L fac[M]={},invfac[M]={};

 L pow_mod(L x,L k){L ans=;for(;k>;k>>=,x=x*x%MOD) if(k&) ans=ans*x%MOD; return ans;}

 L C(int n,int m){return fac[n]*invfac[m]%MOD*invfac[n-m]%MOD;}

 void change(L a[],int n){

     for(int i=,j=;i<n-;i++){

         if(i<j) swap(a[i],a[j]);

         int k=n>>;

         while(j>=k) j-=k,k>>=;

         j+=k;

     }

 }

 void NTT(L a[],int n,int on){

     change(a,n);

     for(int h=;h<=n;h<<=){

         L wn=pow_mod(G,(MOD-)/h);

         for(int j=;j<n;j+=h){

             L w=;

             for(int k=j;k<j+(h>>);k++){

                 L u=a[k],t=a[k+(h>>)]*w%MOD;

                 a[k]=(u+t)%MOD;

                 a[k+(h>>)]=(u-t+MOD)%MOD;

                 w=w*wn%MOD;

             }

         }

     }

     if(on==-){

         reverse(a+,a+n);

         L INV=pow_mod(n,MOD-);

         for(int i=;i<n;i++) a[i]=a[i]*INV%MOD;

     }

 }

 L a[M]={},b[M]={},s[M]={},nc[M]={};

 int main(){

     fac[]=; for(int i=;i<M;i++) fac[i]=fac[i-]*i%MOD;

     invfac[M-]=pow_mod(fac[M-],MOD-);

     for(int i=M-;~i;i--) invfac[i]=invfac[i+]*(i+)%MOD;

     L n,k,ans=; cin>>n>>k;

     if(k==) return printf("%lld\n",n*pow_mod(,(n-)*n/)%MOD);

     for(L i=,mul=;i<k;i++){

         mul=mul*(n-i-)%MOD;

         nc[i+]=mul*pow_mod(,n-i-)%MOD;

     }

     for(int i=;i<=k;i++){

         a[i]=pow_mod(MOD-,i)*invfac[i]%MOD;

         b[i]=pow_mod(i,k)*invfac[i]%MOD;

     }

     int len=; while(k*>=len) len<<=;

     NTT(a,len,); NTT(b,len,);

     for(int i=;i<len;i++) s[i]=a[i]*b[i]%MOD;

     NTT(s,len,-);

     for(int i=k+;i<len;i++) s[i]=;

     for(int i=;i<=k;i++)

     (ans+=nc[i]*s[i])%=MOD;

     cout<<ans*n%MOD*pow_mod(,(n*(n-)/-(n-)))%MOD<<endl;

 }

巴特西

【xsy1301】原题的价值组合数+斯特林数+FFT

最新文章

热门文章

巴特西

【xsy1301】 原题的价值 组合数+斯特林数+FFT

最新文章

热门文章

【xsy1301】原题的价值组合数+斯特林数+FFT