题目概述

一个 $n$ 个点的简单无向图的价值定义为每个点度数 $K$ 次方的和，求所有 $n$ 个点的简单无向图的价值的和。

解题报告

只需要知道这两个前置姿势，这道题就很可做了：

$$ S(n,m)={1\over m!}\sum_{i=0}^{m}(-1)^i{m\choose i}(m-i)^n\\ n^k=\sum_{i=0}^{min\{n,k\}}S(k,i)i!{n\choose i} $$

其中 $S(n,m)​$ 表示第二类斯特林数，证明：

1. 第一个式子是个容斥，$i$ 枚举的是空盒子的个数，那么 $n$ 个球可以在其他盒子乱放，但由于第二类斯特林数表示的是相同盒子，所以最后要除以 $m!$ 。
2. 第二个式子左边表示 $k$ 个不同的球放进 $n$ 个不同的盒子的方案数，右边枚举了非空盒子的个数 $i$ ，那么把 $k$ 个球放入这 $i$ 个盒子，由于第二类斯特林数表示的是相同盒子，所以还要乘上 $i!$ 。

很明显每个点的权值和图没有太大关系，我们可以直接对于每个点进行计算，又可以发现所有点的价值是一样的，所以只需要考虑一个点，从而写出最简单的式子：

$$ n2^{{n\choose 2}-(n-1)}\sum_{i=0}^{n-1}i^K{n-1\choose i} $$

这个式子的意思就是枚举这个点的度数，然后其他无关的边随便选不选。

我们令 $t=n-1$ ，只考虑后面的式子，用第二类斯特林数代掉不可化简的 $i^K$ ：

$$ \sum_{i=0}^{t}{t\choose i}\sum_{j=0}^{min\{i,K\}}S(K,j)j!{i\choose j} $$

发现大多是和 $j$ 有关的，因此考虑 $j$ 提前：

$$ \sum_{j=0}^{min\{t,K\}}S(K,j)j!\sum_{i=j}^{t}{t\choose i}{i\choose j}\\ \sum_{j=0}^{min\{t,K\}}S(K,j)j!\sum_{i=j}^{t}{t\choose j}{t-j\choose i-j}\\ \sum_{j=0}^{min\{t,K\}}S(K,j)j!{t\choose j}\sum_{i=0}^{t-j}{t-j\choose i}\\ \sum_{j=0}^{min\{t,K\}}S(K,j)j!{t\choose j}2^{t-j}\\ \sum_{j=0}^{min\{t,K\}}S(K,j){t!\over(t-j)!}2^{t-j}\\ $$

我们只要求出 $S(K,0\sim K)$ ，就可以算上面那个式子了，根据：

$$ \begin{aligned} S(n,m)&={1\over m!}\sum_{i=0}^{m}(-1)^i{m\choose i}(m-i)^n\\ &=\sum_{i=0}^{m}{(-1)^i\over i!}{(m-i)^n\over(m-i)!} \end{aligned} $$

这就是个卷积形式，直接NTT。

示例程序

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int maxk=1<<19,MOD=998244353;

int n,K,fac[maxk+5],INV[maxk+5],S[maxk+5],rev[maxk+5],pw[2][maxk+5],ans;

inline int Pow(int w,LL b) {int s;for (s=1;b;b>>=1,w=(LL)w*w%MOD) if (b&1) s=(LL)s*w%MOD;return s;}
inline void Pre(int n){
    for (int i=1;i<n;i++) rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
    for (int i=2;i<=n;i<<=1) pw[0][i]=Pow(3,(MOD-1)/i),pw[1][i]=Pow(pw[0][i],MOD-2);
}
inline void AMOD(int &x,int tem) {if ((x+=tem)>=MOD) x-=MOD;}
inline void NTT(int *a,int n,int f){
    for (int i=0;i<n;i++) if (i<rev[i]) swap(a[i],a[rev[i]]);
    for (int k=1;k<n;k<<=1){
        int gn=pw[f<0][k<<1],g=1,x,y;
        for (int i=0;i<n;i+=k<<1,g=1)
            for (int j=0;j<k;j++,g=(LL)g*gn%MOD)
                x=a[i+j],y=(LL)a[i+j+k]*g%MOD,AMOD(a[i+j]=x,y),AMOD(a[i+j+k]=x,MOD-y);
    }if (f<0) for (int i=0,INV=Pow(n,MOD-2);i<n;i++) a[i]=(LL)a[i]*INV%MOD;
}
inline void Make(int n){
    INV[0]=INV[1]=1;for (int i=2;i<=n;i++) INV[i]=(LL)(MOD-MOD/i)*INV[MOD%i]%MOD;
    fac[0]=1;for (int i=1;i<=n;i++) fac[i]=(LL)fac[i-1]*i%MOD,INV[i]=(LL)INV[i]*INV[i-1]%MOD;
    static int F[maxk+5],G[maxk+5];int t;for (t=1;t<=(n<<1);t<<=1);
    for (int i=0;i<=n;i++) F[i]=(LL)(i&1?MOD-1:1)*INV[i]%MOD,G[i]=(LL)Pow(i,n)*INV[i]%MOD;
    for (int i=n+1;i<t;i++) F[i]=G[i]=0;Pre(t);NTT(F,t,1);NTT(G,t,1);
    for (int i=0;i<t;i++) S[i]=(LL)F[i]*G[i]%MOD;NTT(S,t,-1);for (int i=n+1;i<t;i++) S[i]=0;
}
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d%d",&n,&K);Make(K);int t=n-1;
    for (int j=0,tem=1;j<=K&&j<=t;tem=(LL)tem*(t-j)%MOD,j++) AMOD(ans,(LL)S[j]*tem%MOD*Pow(2,t-j)%MOD);
    ans=(LL)ans*n%MOD*Pow(2,(LL)(n-2)*(n-1)>>1)%MOD;printf("%d\n",ans);return 0;
}