题意：定义一个无向图的权值为图中形为树的连通块数量的$k$次方，求所有$n$个点有标号的简单无向图的权值之和。
这个题还是很妙的啊……(好吧，其实只有最后的复合函数求导比较有意思……)
先套路一发，定义答案的$EGF$为$F(x)$一棵树的$EGF$为$T(x)$，每个连通块都不是树的$EGF$为$G(x)$，强制连通的无向图的$EGF$为$H(x)$，显然有
\begin{align}F(x)=\left(\sum_{i\ge 0}\frac{i^k T(x)^i}{i!}\right)G(x)\end{align}
意思就是枚举树的数量，统计数量之后乘上贡献，左边要除以$i!$是为了去重(因为几个树组成的图是集合，不是序列，元素没有顺序)。
根据一些简单的知识不难得到以下结论：
$[x^n]T(x)=n^{n-2}$
$G(x)=\exp(H(x)-T(x))$(因为每个连通块都不能是树，那么我们用连通图个数减掉树的个数，再用这个东西搞一个集合即可，不难发现就是对一个连通块的$EGF$做一下$\exp$的结果。)
$H(x)$可以跑多项式$\ln$之类的东西得到(参见城市规划的做法)，那么后面的$G(x)$就好算了，然后再解决前面的那个东西就可以$O(n)$得出最后的答案了(因为只要求一项，所以暴力求出卷积的第$n$项即可)。
定义
\begin{align}A_k(x)=\sum_{i\ge 0}\frac{i^k T(x)^i}{i!}\end{align}
注意到$A_k(x)$其实是一个复合函数，那么假设有$f(T)=A_k(x)$，我们可以尝试对$f(T)$求个导，而根据复合函数求导法则($(f(g(x)))’=f’(g(x))g’(x)$)有$[T^i]f’(T)=\frac{i^k T(x)^{i-1}T'(x)i}{i!}=T'(x)\frac{i^{k+1}T(x)^{i-1}}{i!}$，因此$[T^i]f’(T)=\frac{i^k T(x)^{i-1}T'(x)i}{i!}=T'(x)\frac{i^{k+1}T(x)^{i-1}}{i!}$。
因为$f(T)$本质就是$A_k(x)$，因此$f’(T)$和$A_k’(x)$是等价的，所以有
\begin{align}A_k'(x)=\frac{T'(x)}{T(x)}\sum_{i\ge 1}\frac{i^{k+1}T(x)^i}{i!}=\frac{T'(x)}{T(x)}A_{k+1}(x)\end{align}
(注意这里不用处理常数项的问题，因为$k>0$时有$[x^0]A_k(x)=0$)
也就是说$A_{k+1}(x)=A_k'(x)\frac{T(x)}{T'(x)}$，那么直接利用这个递推$k$次即可，边界也不难得到：
\begin{align}A_0(x)=\sum_{i\ge 0}\frac{i^0 T(x)^i}{i!}=\exp(T(x))\end{align}
然后就可以做了，复杂度$O(kn\log n)$，因为$\exp$只需要做两次，所以常数还是不大的。
(虽然比起NTT优化DP的做法来说代码长还跑得慢……)
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=,p=,g=;
void NTT(int*,int,int);
void getexp(int*,int*,int);
void getln(int*,int*,int);
void getinv(int*,int*,int);
void getderivative(int*,int*,int);
void getintegrate(int*,int*,int);
int qpow(int,int,int);
int n,N=,k,A[maxn],B[maxn],C[maxn],T[maxn],G[maxn],fac[maxn],fac_inv[maxn],inv[maxn],ans=;
int main(){
scanf("%d%d",&n,&k);
while(N<=n)N<<=;
fac[]=fac_inv[]=;
for(int i=;i<N;i++)fac[i]=(long long)fac[i-]*i%p;
fac_inv[N-]=qpow(fac[N-],p-,p);
for(int i=N-;i;i--)fac_inv[i]=(long long)fac_inv[i+]*(i+)%p;
for(int i=;i<N;i++)inv[i]=(long long)fac_inv[i]*fac[i-]%p;
T[]=G[]=;
for(int i=;i<=n;i++)T[i]=(long long)qpow(i,i-,p)*fac_inv[i]%p;
for(int i=;i<=n;i++)G[i]=(long long)qpow(,(((long long)i*(i-))>>)%(p-),p)*fac_inv[i]%p;
getln(G,B,N);
for(int i=;i<N;i++)B[i]=(B[i]-T[i]+p)%p;
getexp(B,G,N);
fill(B,B+(N<<),);
getderivative(T,B,N);
getinv(B,C,N);
copy(T,T+N,B);
NTT(B,N<<,);
NTT(C,N<<,);
for(int i=;i<(N<<);i++)C[i]=(long long)B[i]*C[i]%p;
NTT(C,N<<,-);
fill(C+N,C+(N<<),);
NTT(C,N<<,);
getexp(T,A,N);
for(int j=;j<=k;j++){
fill(B,B+(N<<),);
getderivative(A,B,N);
NTT(B,N<<,);
for(int i=;i<(N<<);i++)B[i]=(long long)B[i]*C[i]%p;
NTT(B,N<<,-);
copy(B,B+N,A);
}
for(int i=;i<=n;i++)ans=(ans+(long long)A[i]*G[n-i]%p)%p;
printf("%d",(int)((long long)ans*fac[n]%p));
return ;
}
void NTT(int *A,int n,int tp){
for(int i=,j=,k;i<n-;i++){
k=n;
do j^=(k>>=);while(j<k);
if(i<j)swap(A[i],A[j]);
}
for(int k=;k<=n;k<<=){
int wn=qpow(g,(tp>?(p-)/k:(p-)/k*(long long)(p-)%(p-)),p);
for(int i=;i<n;i+=k){
int w=;
for(int j=;j<(k>>);j++,w=(long long)w*wn%p){
int a=A[i+j],b=(long long)w*A[i+j+(k>>)]%p;
A[i+j]=(a+b)%p;
A[i+j+(k>>)]=(a-b+p)%p;
}
}
}
if(tp<){
int inv=qpow(n,p-,p);
for(int i=;i<n;i++)A[i]=(long long)A[i]*inv%p;
}
}
void getexp(int *A,int *C,int n){
static int B[maxn];
fill(C,C+(n<<),);
C[]=;
for(int k=;k<=n;k<<=){
getln(C,B,k);
for(int i=;i<k;i++)B[i]=(A[i]-B[i]+p)%p;
B[]=(B[]+)%p;
NTT(B,k<<,);
NTT(C,k<<,);
for(int i=;i<(k<<);i++)C[i]=(long long)B[i]*C[i]%p;
NTT(C,k<<,-);
fill(C+k,C+(k<<),);
}
}
void getln(int *A,int *C,int n){
static int B[maxn];
getderivative(A,B,n);
fill(B+n,B+(n<<),);
getinv(A,C,n);
NTT(B,n<<,);
NTT(C,n<<,);
for(int i=;i<(n<<);i++)B[i]=(long long)B[i]*C[i]%p;
NTT(B,n<<,-);
getintegrate(B,C,n);
fill(C+n,C+(n<<),);
}
void getinv(int *A,int *C,int n){
static int B[maxn];
fill(C,C+(n<<),);
C[]=qpow(A[],p-,p);
for(int k=;k<=n;k<<=){
copy(A,A+k,B);
fill(B+k,B+(k<<),);
NTT(B,k<<,);
NTT(C,k<<,);
for(int i=;i<(k<<);i++)C[i]=C[i]*((-(long long)C[i]*B[i]%p+p)%p)%p;
NTT(C,k<<,-);
fill(C+k,C+(k<<),);
}
}
void getderivative(int *A,int *C,int n){
for(int i=;i<n;i++)C[i-]=(long long)A[i]*i%p;
C[n-]=;
}
void getintegrate(int *A,int *C,int n){
for(int i=;i<n;i++)C[i]=(long long)A[i-]*inv[i]%p;
C[]=;
}
int qpow(int a,int b,int p){
int ans=;
for(;b;b>>=,a=(long long)a*a%p)if(b&)ans=(long long)ans*a%p;
return ans;
}
ps：代码里把每次乘的$\frac{T(x)}{T’(x)}$算出来之后直接存它的$DFT$了，这样每次乘的时候就只需要对$A_k(x)$做$DFT$和$IDFT$了，可以减小很多常数。
这个题给我的两点启发：
1.看见跟前面那半类似的式子就去试试求导和积分
2.牢记复合函数求导法则(论不学文化课的危害……)