不难想到考虑每个点的贡献，ans=n*sigema(1~n)i C(n-1,i)*(2^C(n-1,2))*i^k

直接套第二类斯特林拆柿子即可。提示:sigema(1~n)i C(n,i)*C(i,j) = C(n,j)*2^(n-j)

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;typedef long long LL;const int _=1e2;const int maxK=2e5+_;const int fbiK=(1<<18)+_;const int mod=998244353;inline int ad(int x,int y){ return (x>=mod-y)?(x-mod+y):x+y;}inline int re(int x,int y){ return (x
           
            0){ if(y&1)r=mu(r,x);x=mu(x,x);y/=2;}return r;}int fac[maxK],fac_inv[maxK],inv[maxK];void yu(int K){ fac[0]=1;for(int i=1;i<=K;i++)fac[i]=mu(fac[i-1],i); fac_inv[K]=qp(fac[K],mod-2); for(int i=K-1;i>=0;i--)fac_inv[i]=mu(fac_inv[i+1],i+1); inv[1]=1;for(int i=2;i<=K;i++)inv[i]=mu(inv[mod%i],mod-mod/i);}namespace GETS2{ int Re[2*fbiK]; void NTT(int *a,int n,int op) { for(int i=0;i
            
             >1]>>1)|((i&1)<<(L-1)); for(int i=0;i<=K;i++) { A[i]=mu((i&1)?mod-1:1,fac_inv[i]); B[i]=mu(qp(i,K),fac_inv[i]); } NTT(A,n,1),NTT(B,n,1); for(int i=0;i