bzoj5093图的价值：多项式，斯特林数（二项式反演）

Description

“简单无向图”是指无重边、无自环的无向图（不一定连通）。 一个带标号的图的价值定义为每个点度数的k次方的和。 给定n和k，请计算所有n个点的带标号的简单无向图的价值之和。

因为答案很大，请对998244353取模输出。$n \le 10^9,k \le 200000$

化学学考时含义推式子+手动打表找规律得到了一个$O(nlogn)$的式子开心的很我以为我要AC了回来看数据范围就升天了。

问NC大神这题用到了什么：斯特林数/伯努利数。然后就自闭了学了一天的知识点还去做了点伯努利数的别的题。

然而最后没想到伯努利数的做法，是用第二类斯特林数解决的。

先列出来答案的式子，分别考虑每个点的贡献：

$ans=2^{\frac{(n-1)(n-2)}{2}} \times n \times \sum\limits_{i=0}^{n} C_{n-1}^i \times i^k$

就是首先在n个点里选出你当前考虑贡献答案的是哪个点，然后在剩余的n-1个点的子图里联通情况随意就是$2^{\frac{(n-1)(n-2)}{2}}$

然后从n-1个点里选出i个与当前贡献答案的点连边，选法是组合数，贡献的价值是$i^k$。

可以发现，这里有个求自然数幂和乘个组合数的形式，而自然数幂和的范围很大不能直接求解。

动用学过的（和刚学的）所有数学知识点看有什么能把幂拆成可以接受的形式。

1，伯努利数：$\sum\limits_{i=1}^{n} i^m = \frac{\sum\limits_{i=1}^{m} B_i \times C_{m+1}^{i} \times n^{m+1-i} }{m+1}$

这不妨是个好主意，但是这道题里要求的是自然数幂乘组合数后再求和，并不能直接适用，所以至少我现在还不会做。

等会上网学习一下再来fix这里。

学习完了，网上并没有这样的做法，但是伯努利数和第二类斯特林数可以互相转化。。。

对这题并没有什么帮助。。。

2，第二类斯特林数：$x^n=\sum\limits_{i=0}^{n} \left \{ ^n_k \right \} \times \frac{x!}{(x-i)!}$

这样的话虽然不能直接求和，但是好歹可以把难以解决的高次幂转化为经常处理的阶乘什么的了。

首先说说关于斯特林数怎么求：先弄明白含义，第二类斯特林数$\left \{ ^n_k \right \}$表示把n个元素放进k个无标号非空集合的方案数。

然后我们再弄几个类似的定义：设f(n,k)表示把n个元素放进k个有编号非空集合的方案数，g(n,k)表示n个元素放进k个有标号可空集合的方案数。

对于是否有编号的问题，其实就是多了个内部顺序，所以$\left \{ ^n_k \right \}=\frac{f(n,k)}{k!}$

然后g其实是可以直接求解的：$g(n,k)=k^n$

然后至于f和g之间的关系，我们可以通过枚举它具体有几个集合是空的，得到$g(n,k)=\sum\limits_{i=0}^{k} C_k^i \times f(n,i)$

就是选出到底哪几个不是空的，在这些非空的里面进行分配。

然后发现这个形式就是二项式反演的基本形式，所以反演它：$f(n,k)=\sum\limits_{i=0}^{k} (-1)^{k-i} \times C_k^i \times g(n,i)$

这样我们就能得到f，进而求解出第二类斯特林数。

总的式子就是$\left \{ ^n_k \right \}=\sum\limits_{i=0}^{k} \frac{(-1)^{k-i} \times i^k}{(k-i)! \times i!}$

这样的话单点求第二类斯特林数就是$O(n)$的了。而上式是个卷积形式，所以求一行第二类斯特林数就可以用NTT在$O(nlogn)$之内解决。

回到这道题来，求解斯特林数的复杂度是$O(klogk)$可以接受，那么现在答案的式子是什么？

$ans=2^{\frac{(n-1)(n-2)}{2}} \times n \times \sum\limits_{i=0}^{n} C_{n-1}^{i} \sum\limits_{j=0}^{k} \left \{ ^k_j \right \} \times \frac{i!}{(i-j)!}$

把各种组合数拆一拆放在一起消一消，得到：$ans=2^{\frac{(n-1)(n-2)}{2}} \times n! \times \sum\limits_{i=0}^{n} \sum\limits_{j=0}^{k} \left \{ ^k_j \right \} \times \frac{1}{(i-j)! \times (n-i-1)!}$

换一下ij的枚举顺序，发现最后那个分母上两个阶乘的底之和是一个与i无关的定值，上下都乘一个$(n-j-1)!$合成一个组合数。它等于$\frac{C_{n-j-1}^{i-j}}{(n-j-1)!}$

然后再套上外面那个求和。。。一行组合数求和得到的是2的次幂，所以这个和式就可以扔掉了得到下面形式：

$ans=2^{\frac{(n-1)(n-2)}{2}} \times n! \times \sum\limits_{j=0}^{k} \frac{\left \{ ^k_j \right \} \times 2^{n-j-1}}{(n-j-1)!} $

现在的瓶颈就在于式子中的两个阶乘不能在合理复杂度内求出。

然而它们一个在分子上，一个在分母上，而且它们底数的差值在k范围内。。。

抵消啊！就剩下一个下降幂了！

所以最后可做的式子就是$2^{\frac{(n-1)(n-2)}{2}} \sum\limits_{j=0}^{k} \left \{ ^k_j \right \} \times 2^{n-j-1} \times n^{\underline{j+1}}$

 #include<cstdio>

 #define int long long

 #define mod 998244353

 #define S 555555

 int n,k,a[S],s[S],len=,fac[S],inv[S],rev[S],dw[S],ans;

 int pow(int b,int t,int a=){for(;t;t>>=,b=b*b%mod)if(t&)a=a*b%mod;return a;}

 void NTT(int *a,int opt){

     for(int i=;i<len;++i)if(rev[i]>i)a[i]^=a[rev[i]]^=a[i]^=a[rev[i]];

     for(int mid=;mid<len;mid<<=)

         for(int i=,t=pow(,(mod-)//mid*opt+mod-);i<len;i+=mid<<)

             for(int j=i,x,y,w=;j<mid+i;++j,w=w*t%mod)

                 x=a[j],y=a[j+mid]*w%mod,a[j]=(x+y)%mod,a[j+mid]=(x-y+mod)%mod;

     if(opt==-)for(int i=,iv=pow(len,mod-);i<len;++i)a[i]=a[i]*iv%mod;

 }

 signed main(){

     scanf("%lld%lld",&n,&k);fac[]=dw[]=;

     while(len<=k<<)len<<=;

     for(int i=;i<len;++i)rev[i]=rev[i>>]>>|(i&?len>>:);

     for(int i=;i<=k;++i)fac[i]=fac[i-]*i%mod;

     inv[k]=pow(fac[k],mod-);

     for(int i=k-;~i;--i)inv[i]=inv[i+]*(i+)%mod;

     for(int i=;i<=k;++i)a[i]=pow(i,k)*inv[i]%mod,s[i]=(i&?mod-:)*inv[i]%mod;

     NTT(a,);NTT(s,);for(int i=;i<len;++i)s[i]=s[i]*a[i]%mod;NTT(s,-);

     for(int i=;i<=k+;++i)dw[i]=dw[i-]*(n+-i)%mod;

     for(int i=;i<=k;++i)ans=(ans+dw[i+]*pow(,n-i-)%mod*s[i])%mod;

     printf("%lld\n",ans*pow(,(n-)*(n-)/)%mod);

 }

真累啊。。。

bzoj5093图的价值：多项式，斯特林数（二项式反演）的相关教程结束。