Description “简单无向图”是指无重边、无自环的无向图（不一定连通）。
一个带标号的图的价值定义为每个点度数的k次方的和。
给定n和k，请计算所有n个点的带标号的简单无向图的价值之和。
因为答案很大，请对998244353取模输出。
Solution 【NTT|[BZOJ]5093: [Lydsy1711月赛]图的价值 NTT+第二类斯特林数】考虑每个点的贡献，容易得到如下式子： a n s = n × 2 n ( n ? 1 ) 2 ? n + 1 ∑ i = 1 n ? 1 C n ? 1 i i k ans=n\times2^{{n(n-1)\over2}-n+1}\sum_{i=1}^{n-1}C_{n-1}^ii^k ans=n×22n(n?1)??n+1i=1∑n?1?Cn?1i?ik
前面的一堆很好算，先丢掉，考虑后面的怎么求。试着用第二类斯特林数把后面的 i k i^k ik展开一下： ∑ i = 1 n ? 1 C n ? 1 i ∑ j = 1 m i n ( n , k ) S ( k , j ) C i j j ! \sum_{i=1}^{n-1}C_{n-1}^i\sum_{j=1}^{min(n,k)}S(k,j)C_i^jj! i=1∑n?1?Cn?1i?j=1∑min(n,k)?S(k,j)Cij?j!交换求和顺序： ∑ j = 1 k S ( k , j ) j ! ( ∑ i ≥ j C n ? 1 i C i j ) \sum_{j=1}^kS(k,j)j!(\sum_{i\ge j} C_{n-1}^iC_i^j) j=1∑k?S(k,j)j!(i≥j∑?Cn?1i?Cij?)
此时发现不会搞了，考虑后面那个东西的组合意义：先从 n ? 1 n-1 n?1个中选出 j j j个，然后剩下的选不选都可以。所以后面的那堆其实等于： C n ? 1 j 2 n ? 1 ? j C_{n-1}^j2^{n-1-j} Cn?1j?2n?1?j
然后我们用容斥求第二类斯特林数的那个式子，用NTT先算出斯特林数，然后再算这个式子就可以了。
Code
#include
using namespace std;
#define LL long long
#define pa pair
const int Maxn=200010;
const int inf=2147483647;
const int mod=998244353,gn=3;
int read()
{
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
return x*f;
}
void upd(int&x,int y){x+=y;
if(x>=mod)x-=mod;
}
void cmin(int&x,int y){x=min(x,y);
}
void cmax(int&x,int y){x=max(x,y);
}
int n,k,A[Maxn<<2],B[Maxn<<2];
int Pow(int x,LL y)
{
if(!y)return 1;
int t=Pow(x,y>>1),re=(LL)t*t%mod;
if(y&1)re=(LL)re*x%mod;
return re;
}
int fac[Maxn],fin[Maxn];
void pre()
{
fac[0]=1;
for(int i=1;
i<=k;
i++)fac[i]=(LL)fac[i-1]*i%mod;
fin[k]=Pow(fac[k],mod-2);
for(int i=k-1;
i>=0;
i--)fin[i]=(LL)fin[i+1]*(i+1)%mod;
}
int C(int n,int m)
{
if(n>1]>>1)|((i&1)*(m>>1)));
for(int i=0;
i<=k;
i++)
if(i&1)A[i]=mod-fin[i];
else A[i]=fin[i];
for(int i=0;
i<=k;
i++)B[i]=(LL)Pow(i,k)*fin[i]%mod;
NTT(A,m,1),NTT(B,m,1);
for(int i=0;
i 
