[BZOJ5093]图的价值(NTT+第二类Stirling数)

挺喜欢的一道题，首先从每个点的贡献的角度考虑并列出式子，然后通过Stirling数将幂数转化为下降幂，再交换求和枚举顺序并用组合数公式化简，最后用Stirling数组合意义公式转化成可以FFT的形式，直接套用NTT即可。

具体参考https://blog.csdn.net/cdsszjj/article/details/79080229

首先第一步列出式子不难想到，然后观察发现这是一个n项求和，显然不能直接做，第二步引入Stirling数，尽量使关于n的项消去。通过把与n有关的项放在等式最后并变形，成功使枚举上界从n变为min(n,k)，大大降低了时间复杂度。但是递推求$O(k)$的Stirling数仍然无法承受，但第二类Stirling数有恰好符合FFT形式的公式，我们另$a[i]=\frac{(-1)^i}{i!}$,$b[i]=\frac{(m-i)^n}{(m-i)!}$，结果就是最基本的FFT形式：$S[n]=\sum_{i=0}^{n}a[i]b[n-i]$。这里将NTT封装起来感觉清晰了不少。

扯几句题外话：

1.设$f(n)=\sum\limits_{i=1}^n(i,n)$，$g(n)=\sum\limits_{d|n}f(d)$，化简$g(n)$。

$$f(n)=\sum\limits_{i=1}^n\sum\limits_{d|i\ d|n}\phi(d)=\sum\limits_{d|n}\phi(d)\frac{n}{d}$$到这里我们可以不断带入化简，但是我们其实可以发现：$$f(n)=\phi*id$$$$g(n)=I*f=I*(\phi*id)=(I*\phi)*id=id*id$$所以$$g(n)=\sum\limits_{d|n}d\frac{n}{d}$$

2.几个组合数化简：$$\sum_{i=0}^nC_n^iC_i^k=C_n^k\sum_{i=k}^nC_{n-k}^{i-k}$$$$\sum_{i=0}^aC_a^iC_b^{k-i}=C_{a+b}^k$$$$\sum_{i=0}^aC_a^iC_a^i=C_{2a}^i$$$$\sum_{i=0}^aC_a^{a-i}C_b^{i+k}=C_{a+b}^{a+k}$$

 #include<cstdio>

 #include<algorithm>

 #define rep(i,l,r) for (int i=l; i<=r; i++)

 typedef long long ll;

 using namespace std;

 const int N=,mod=,G=;

 int n,k,ans,a[N],s[N],fac[N],fin[N],fn[N];

 int ksm(int a,ll b){

     int res;

     for (res=; b; a=(1ll*a*a)%mod,b>>=)

         if (b & ) res=(1ll*res*a)%mod;

     return res;

 }

 namespace NTT{

     int n,L,rev[N];

     void init(int m){

         n=; L=;

         while (n<=m) n<<=,L++;

         for (int i=; i<n; i++) rev[i]=(rev[i>>]>>)|((i&)<<(L-));

     }

     void DFT(int a[],int f){

         for (int i=; i<n; i++) if (i<rev[i]) swap(a[i],a[rev[i]]);

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

             int wn=ksm(G,(f==)?(mod-)/(i<<):(mod-)-(mod-)/(i<<));

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

                 int w=;

                 for (int k=; k<i; k++,w=1ll*w*wn%mod){

                     int x=a[j+k],y=1ll*w*a[i+j+k]%mod; a[j+k]=(x+y)%mod; a[i+j+k]=(x-y+mod)%mod;

                 }

             }

         }

         if (f==) return;

         int inv=ksm(n,mod-);

         for (int i=; i<n; i++) a[i]=1ll*a[i]*inv%mod;

     }

     void multi(int a[],int b[]){

         DFT(a,); DFT(b,);

         for (int i=; i<n; i++) a[i]=(1ll*a[i]*b[i])%mod;

         DFT(a,-);

     }

 }

 int main(){

     freopen("bzoj5093.in","r",stdin);

     freopen("bzoj5093.out","w",stdout);

     scanf("%d%d",&n,&k); n--; fac[]=fin[]=fn[]=;

     rep(i,,k) fac[i]=1ll*fac[i-]*i%mod;

     fin[k]=ksm(fac[k],mod-);

     for (int i=k-; i; i--) fin[i]=(1ll*fin[i+]*(i+))%mod;

     rep(i,,k) fn[i]=(1ll*fn[i-]*(n-i+))%mod;

     rep(i,,k) s[i]=(((i&)?-:)*fin[i]+mod)%mod;

     rep(i,,k) a[i]=(1ll*ksm(i,k)*fin[i])%mod;

     NTT::init(*k+); NTT::multi(s,a);

     rep(i,,min(n,k)) ans=(ans+1ll*s[i]*fac[i]%mod*fn[i]%mod*fin[i]%mod*ksm(,n-i))%mod;

     printf("%lld\n",1ll*ans*(n+)%mod*ksm(,1ll*n*(n-)/)%mod);

     return ;

 }