显然只需要考虑一个点(再乘n)，那么枚举这个点的度数，另外的$frac{(n-1)(n-2)}{2}$条边是随意连的，而这个点连出去的边又和其余$n-1$个点产生组合，所以答案就是
$n*frac{(n-1)(n-2)}{2}*sumlimits_{i=0}^{n-1}C_{n-1}^i i^k$
运用第二类斯特林数和自然数幂的关系展开$i^k$，然后发现后面那一坨只要算到$min(n-1,k)$就可以了(再往后斯特林数就成零了)
于是问题变成了快速求一行第二类斯特林数，多项式卷积即可
1 #include<cmath> 2 #include<cstdio> 3 #include<cctype> 4 #include<cstring> 5 #include<algorithm> 6 using namespace std; 7 const int N=800006,mod=998244353; 8 int fac[N],inv[N],rev[N],a[N],b[N]; 9 int n,m,k,G,Gi,C,ans,pw[30][2]; 10 void Add(int &x,int y) 11 { 12 x+=y; 13 if(x>=mod) x-=mod; 14 } 15 int Qpow(int x,int p) 16 { 17 if(p==0) return 1; 18 if(p==1) return x; 19 int tmp=Qpow(x,p/2); 20 return p%2?1ll*tmp*tmp%mod*x%mod:1ll*tmp*tmp%mod; 21 } 22 void Prework() 23 { 24 register int i; 25 scanf("%d%d",&n,&k); 26 fac[0]=inv[0]=1; 27 for(i=1;i<=k;i++) fac[i]=1ll*fac[i-1]*i%mod; 28 inv[k]=Qpow(fac[k],mod-2); 29 for(i=k-1;i;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod; 30 for(i=0;i<=k;i++) 31 { 32 a[i]=i%2?mod-inv[i]:inv[i]; 33 b[i]=1ll*Qpow(i,k)*inv[i]%mod; 34 } 35 m=1; while(m<=2*k) m<<=1; 36 for(i=1;i<=m;i++) 37 rev[i]=(rev[i>>1]>>1)+(i&1)*(m>>1); 38 G=3,Gi=Qpow(G,mod-2); 39 for(int i=1;i<=24;i++) 40 { 41 pw[i][0]=Qpow(G,(mod-1)/(1<<i)); 42 pw[i][1]=Qpow(Gi,(mod-1)/(1<<i)); 43 } 44 } 45 void Trans(int *arr,int len,int typ) 46 { 47 register int i,j,k; 48 for(i=0;i<len;i++) 49 if(rev[i]>i) swap(arr[rev[i]],arr[i]); 50 for(i=2;i<=len;i<<=1) 51 { 52 int lth=i>>1,ort=pw[(int)log2(i)][typ==-1]; 53 for(j=0;j<len;j+=i) 54 { 55 int ori=1,tmp; 56 for(k=j;k<j+lth;k++,ori=1ll*ori*ort%mod) 57 { 58 tmp=1ll*ori*arr[k+lth]%mod; 59 arr[k+lth]=(arr[k]-tmp+mod)%mod; 60 arr[k]=(arr[k]+tmp)%mod; 61 } 62 } 63 } 64 if(typ==-1) 65 { 66 int Ni=Qpow(len,mod-2); 67 for(i=0;i<=len;i++) 68 arr[i]=1ll*arr[i]*Ni%mod; 69 } 70 } 71 int main() 72 { 73 register int i; 74 Prework(); 75 Trans(a,m,1),Trans(b,m,1); 76 for(i=0;i<m;i++) a[i]=1ll*a[i]*b[i]%mod; 77 Trans(a,m,-1),C=1; //for(int i=0;i<=m;i++) printf("%d ",a[i]); 78 // for(int i=1;i<=n;i++) printf("%d %d ",fac[i],inv[i]); 79 for(i=0;i<=min(n-1,k);i++) 80 { 81 Add(ans,1ll*a[i]*fac[i]%mod*C%mod*Qpow(2,n-i-1)%mod); 82 C=1ll*C*(n-i-1)%mod*Qpow(i+1,mod-2)%mod; 83 } 84 int pw=1ll*(n-1)*(n-2)/2%(mod-1); 85 printf("%lld",1ll*ans*n%mod*Qpow(2,pw)%mod); 86 return 0; 87 }