Description
化学学考时含义推式子+手动打表找规律得到了一个$O(nlogn)$的式子开心的很我以为我要AC了回来看数据范围就升天了。
问NC大神这题用到了什么：斯特林数/伯努利数。然后就自闭了学了一天的知识点还去做了点伯努利数的别的题。
然而最后没想到伯努利数的做法，是用第二类斯特林数解决的。
先列出来答案的式子，分别考虑每个点的贡献：
$ans=2^{\frac{(n-1)(n-2)}{2}} \times n \times \sum\limits_{i=0}^{n} C_{n-1}^i \times i^k$
就是首先在n个点里选出你当前考虑贡献答案的是哪个点，然后在剩余的n-1个点的子图里联通情况随意就是$2^{\frac{(n-1)(n-2)}{2}}$
然后从n-1个点里选出i个与当前贡献答案的点连边，选法是组合数，贡献的价值是$i^k$。
可以发现，这里有个求自然数幂和乘个组合数的形式，而自然数幂和的范围很大不能直接求解。
动用学过的（和刚学的）所有数学知识点看有什么能把幂拆成可以接受的形式。
1，伯努利数：$\sum\limits_{i=1}^{n} i^m = \frac{\sum\limits_{i=1}^{m} B_i \times C_{m+1}^{i} \times n^{m+1-i} }{m+1}$
这不妨是个好主意，但是这道题里要求的是自然数幂乘组合数后再求和，并不能直接适用，所以至少我现在还不会做。
等会上网学习一下再来fix这里。
2，第二类斯特林数：$x^n=\sum\limits_{i=0}^{n} \left \{ ^n_k \right \} \times \frac{x!}{(x-i)!}$
这样的话虽然不能直接求和，但是好歹可以把难以解决的高次幂转化为经常处理的阶乘什么的了。
首先说说关于斯特林数怎么求：先弄明白含义，第二类斯特林数$\left \{ ^n_k \right \}$表示把n个元素放进k个无标号非空集合的方案数。
然后我们再弄几个类似的定义：设f(n,k)表示把n个元素放进k个有编号非空集合的方案数，g(n,k)表示n个元素放进k个有标号可空集合的方案数。
对于是否有编号的问题，其实就是多了个内部顺序，所以$\left \{ ^n_k \right \}=\frac{f(n,k)}{k!}$
然后g其实是可以直接求解的：$g(n,k)=k^n$
然后至于f和g之间的关系，我们可以通过枚举它具体有几个集合是空的，得到$g(n,k)=\sum\limits_{i=0}^{k} C_k^i \times f(n,i)$
就是选出到底哪几个不是空的，在这些非空的里面进行分配。
然后发现这个形式就是二项式反演的基本形式，所以反演它：$f(n,k)=\sum\limits_{i=0}^{k} (-1)^{k-i} \times C_k^i \times g(n,i)$
这样我们就能得到f，进而求解出第二类斯特林数。
总的式子就是$\left \{ ^n_k \right \}=\sum\limits_{i=0}^{k} \frac{(-1)^{k-i} \times i^k}{(k-i)! \times i!}$
这样的话单点求第二类斯特林数就是$O(n)$的了。而上式是个卷积形式，所以求一行第二类斯特林数就可以用NTT在$O(nlogn)$之内解决。
回到这道题来，求解斯特林数的复杂度是$O(klogk)$可以接受，那么现在答案的式子是什么？
$ans=2^{\frac{(n-1)(n-2)}{2}} \times n \times \sum\limits_{i=0}^{n} C_{n-1}^{i} \sum\limits_{j=0}^{k} \left \{ ^k_j \right \} \times \frac{i!}{(i-j)!}$
把各种组合数拆一拆放在一起消一消，得到：$ans=2^{\frac{(n-1)(n-2)}{2}} \times n! \times \sum\limits_{i=0}^{n} \sum\limits_{j=0}^{k} \left \{ ^k_j \right \} \times \frac{1}{(i-j)! \times (n-i-1)!}$
换一下ij的枚举顺序，发现最后那个分母上两个阶乘的底之和是一个与i无关的定值，上下都乘一个$(n-j-1)!$合成一个组合书。它等于$\frac{C_{n-j-1}^{i-j}}{(n-j-1)!}$
然后再套上外面那个求和。。。一行组合数求和得到的是2的次幂，所以这个和式就可以扔掉了得到下面形式：
$ans=2^{\frac{(n-1)(n-2)}{2}} \times n! \times \sum\limits_{j=0}^{k} \frac{\left \{ ^k_j \right \} \times 2^{n-j-1}}{(n-j-1)!} $
现在的瓶颈就在于式子中的两个阶乘不能在合理复杂度内求出。
然而它们一个在分子上，一个在分母上，而且它们底数的差值在k范围内。。。
抵消啊！就剩下一个下降幂了！
所以最后可做的式子就是$2^{\frac{(n-1)(n-2)}{2}} \sum\limits_{j=0}^{k} \left \{ ^k_j \right \} \times 2^{n-j-1} \times n^{\underline{j+1}}$
1 #include<cstdio> 2 #define int long long 3 #define mod 998244353 4 #define S 555555 5 int n,k,a[S],s[S],len=1,fac[S],inv[S],rev[S],dw[S],ans; 6 int pow(int b,int t,int a=1){for(;t;t>>=1,b=b*b%mod)if(t&1)a=a*b%mod;return a;} 7 void NTT(int *a,int opt){ 8 for(int i=1;i<len;++i)if(rev[i]>i)a[i]^=a[rev[i]]^=a[i]^=a[rev[i]]; 9 for(int mid=1;mid<len;mid<<=1) 10 for(int i=0,t=pow(3,(mod-1)/2/mid*opt+mod-1);i<len;i+=mid<<1) 11 for(int j=i,x,y,w=1;j<mid+i;++j,w=w*t%mod) 12 x=a[j],y=a[j+mid]*w%mod,a[j]=(x+y)%mod,a[j+mid]=(x-y+mod)%mod; 13 if(opt==-1)for(int i=0,iv=pow(len,mod-2);i<len;++i)a[i]=a[i]*iv%mod; 14 } 15 signed main(){ 16 scanf("%lld%lld",&n,&k);fac[0]=dw[0]=1; 17 while(len<=k<<1)len<<=1; 18 for(int i=1;i<len;++i)rev[i]=rev[i>>1]>>1|(i&1?len>>1:0); 19 for(int i=1;i<=k;++i)fac[i]=fac[i-1]*i%mod; 20 inv[k]=pow(fac[k],mod-2); 21 for(int i=k-1;~i;--i)inv[i]=inv[i+1]*(i+1)%mod; 22 for(int i=0;i<=k;++i)a[i]=pow(i,k)*inv[i]%mod,s[i]=(i&1?mod-1:1)*inv[i]%mod; 23 NTT(a,1);NTT(s,1);for(int i=0;i<len;++i)s[i]=s[i]*a[i]%mod;NTT(s,-1); 24 for(int i=1;i<=k+1;++i)dw[i]=dw[i-1]*(n+1-i)%mod; 25 for(int i=0;i<=k;++i)ans=(ans+dw[i+1]*pow(2,n-i-1)%mod*s[i])%mod; 26 printf("%lld\n",ans*pow(2,(n-1)*(n-2)/2)%mod); 27 }