Description “简单无向图”是指无重边、无自环的无向图（不一定连通）。 一个带标号的图的价值定义为每个点度数的k次方的和。 给定n和k，请计算所有n个点的带标号的简单无向图的价值之和。 因为答案很大，请对998244353取模输出。 Input 第一行包含两个正整数n,k(1<=n<=10^9,1<=k<=200000)。
做法： 用第二类斯特林数推公式 题解
关于第二类斯特林数 留坑，有空了好好学一波，但是这些公式要怎么才记得住！ 没事，有板子，重点会用！
一个简单的模板我却调了很久，写多项式的能力很差！
#include <bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<=b;++i) #define per(i,a,b) for(int i=a;i>=b;--i) #define repd(i,a,b) for(int i=a;i>=b;--i) #define rvc(i,S) for(int i=0;i<(int)S.size();++i) #define fore(i,x) for(int i = head[x] ; i ; i = e[i].next) #define mp make_pair #define pb push_back #define fi first #define se second #define debug(...) fprintf(stderr,__VA_ARGS__) #define lowbit(x) (x&(-x)) using namespace std; #define maxn 600020 typedef long long ll; typedef vector <ll> Poly; const ll mod = 998244353; const ll G = 3 , gi = 3; ll ginv; ll w[2][maxn]; namespace Polygen { inline ll add(ll x,ll y){ x += y; if ( x >= mod ) x -= mod; return x; } inline ll sub(ll x,ll y){ x -= y; if ( x < 0 ) x += mod; return x; } inline ll power(ll x,ll y){ ll res = 1; while ( y ){ if ( y & 1 ) res = res * x % mod; x = x * x % mod; y >>= 1; } return res; } void init(){ ginv = power(G,mod - 2); for (int i = 1; i < (1 << 19); i <<= 1) { ll wn = power(gi, (mod - 1) / (i << 1)); for (int j = 0; j < i; j++) { w[1][i + j] = (j ? wn * w[1][i + j - 1] % mod : 1); } wn = power(gi, mod - 1 - (mod - 1) / (i << 1)); for (int j = 0; j < i; j++) { w[0][i + j] = (j ? wn * w[0][i + j - 1] % mod : 1); } } } void print(const Poly &p){ cout<<p.size()<<endl; rvc(i,p) cout<<p[i]<<" "; cout<<endl; } inline void NTT(Poly &a,int len,int fl) { //预处理原根快了一倍！ fl = max(0 , fl); int i , j , k; for (j = 1 , i = ( len >> 1 ) ; j < len; j++) { if (j > i) swap(a[i] , a[j]); for (k = (len>>1) ; k & i; k >>= 1 ) i ^= k; i ^= k; } for (i = 1; i < len; i <<= 1) { for (j = 0; j < len; j += i << 1) { for (k = 0; k < i; k++) { ll x = a[j + k], y = a[j + k + i] * w[fl][i + k] % mod; a[j + k] = add( x , y ); a[j + k + i] = sub( x , y ); } } } if (fl == 0) { ll inv = power(len , mod-2); for (int i = 0; i < len; i++) a[i] = a[i] * inv % mod; } } } using namespace Polygen; Poly S,f,g; int n,k; ll fac[maxn],inv[maxn],pow2[maxn],fac2[maxn]; void pre(){ fac[0] = inv[0] = pow2[0] = fac2[0] = 1; rep(i,1,k) fac[i] = fac[i - 1] * i % mod , inv[i] = power(fac[i],mod - 2) , pow2[i] = pow2[i - 1] * 2 % mod; // cout<<f.size()<<" "<<g.size()<<endl; rep(i,1,k) fac2[i] = fac2[i - 1] * (n - i) % mod; rep(i,0,k){ if ( i & 1 ) f[i] = (mod - inv[i]); else f[i] = inv[i]; g[i] = power(i,k) * inv[i] % mod; // cout<<f[i]<<" "<<g[i]<<endl; } } inline ll C(int n,int m){ if ( n < m ) return 0; return fac2[m] * inv[m] % mod; } int main(){ // freopen("input.txt","r",stdin); init(); scanf("%d %d",&n,&k); int len = ceil(log2(k * 2)); len = 1 << len; f.resize(len) , g.resize(len) , S.resize(len); pre(); NTT(f,len,1) , NTT(g,len,1); rep(i,0,len - 1) S[i] = f[i] * g[i] % mod; NTT(S,len,-1); S[0] = 0; // rep(i,0,min(k,100)) cout<<S[i]<<" "; // cout<<endl; ll ans = 0; rep(i,0,min(n - 1,k)){ ans = (ans + S[i] * fac[i] % mod * C(n - 1,i) % mod * power(2,n - 1 - i)) % mod; } ans = ans * n % mod * power(2,(ll)(n - 1) * (n - 2) / 2 % (mod - 1)) % mod; cout<<ans<<endl; }