题目大意
定义一张无向图的价值为其联通块个数的$k$次方，求$n$个点构成的无向图的价值的期望。
$n leq 5*10^4,k leq 15$
题解
首先看到这个恶心人的$k$次方就会想要拆开。
那么设某张图的联通块个数为$T$，那么它的价值为
$$Tk=sum_{i=1}k{T choose i}{k race i}i!$$
考虑其组合意义，可以将上式理解为枚举$T$中所有大小为$i$的联通块集合，并对每种大小乘以${k race i}i!$的贡献。
于是，可以改变枚举顺序，考虑枚举联通块集合，再计算这个集合在多少张图上存在，最后乘上${k race i}i!$即可。
于是设$g_t$为包含$t$个联通块的无向连通图的方案数的生成函数。
易知$g_1$便是经典的无向连通图的生成函数，可以用分治FFT、多项式求逆、多项式求$ln$等方法来解决。
而对于剩下$t geq 2$的$g_t$来说，有:
$$g_t(n)=sum_{i=1}^n{n-1 choose i-1} g_1(i) g_{t-1}(n-i)$$
拆一下组合数便可得到可以FFT的式子了。
最后计算答案的式子为:
$$ans=sum_{i=1}^{k}{k race i}i!sum_{j=1}ng_i(n-j)*2{j choose 2}$$
后边的求和符号在用FFT预处理后可以$O(1)$查询。
于是就完成了，使用多项式求$ln$的情况下预处理复杂度$O(knlog n)$，单次询问$O(k)$。
代码:
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
const int K=17;
const int M=5e4+5;
const int N=2e5+9;
const int md=1004535809;
int rev[N],n,m,k;
ll fac[N],inv[N];
ll g[K][N],s[K][K];
ll t[K][N],h[N],f[N];
inline ll qpow(ll a,ll b)
{
ll ret=1;
while(b)
{
if(b&1)ret=ret*a%md;
a=a*a%md;b>>=1;
}
return ret;
}
inline ll c(ll a,ll b){return fac[a]*inv[b]%md*inv[a-b]%md;}
inline void initrev(int n)
{
for(int i=0;i<n;i++)
rev[i]=(rev[i>>1]>>1)|((i&1)*(n>>1));
}
inline void ntt(ll *a,int n,bool f)
{
for(int i=0;i<n;i++)if(i<rev[i])swap(a[i],a[rev[i]]);
for(int h=2;h<=n;h<<=1)
{
ll w=qpow(3,(md-1)/h);
if(f)w=qpow(w,md-2);
for(int j=0;j<n;j+=h)
{
ll wn=1ll,x,y;
for(int k=j;k<j+(h>>1);k++)
{
x=a[k],y=wn*a[k+(h>>1)]%md;
a[k]=(x+y)%md;a[k+(h>>1)]=(x-y+md)%md;
wn=wn*w%md;
}
}
}
if(f)
for(ll i=0,inv=qpow(n,md-2);i<n;i++)
a[i]=a[i]*inv%md;
}
inline void mul(ll *a,int n,ll *b,int m,ll *c)
{
static ll d[N],e[N],l;
for(l=1;l<=n+m;l<<=1);initrev(l);
for(int i=0;i<n;i++)d[i]=a[i];
for(int i=n;i<l;i++)d[i]=0;
for(int i=0;i<m;i++)e[i]=b[i];
for(int i=m;i<l;i++)e[i]=0;
ntt(d,l,0);ntt(e,l,0);
for(int i=0;i<l;i++)
d[i]=d[i]*e[i]%md;
ntt(d,l,1);
for(int i=0;i<n+m-1;i++)
c[i]=d[i];
}
inline void cinv(ll *a,ll *b,int n)
{
static ll c[N];
if(n==0){b[0]=qpow(a[0],md-2);return;}
cinv(a,b,n>>1);
for(int i=0;i<n;i++)c[i]=a[i];
for(int i=n;i<n*2;i++)c[i]=0;
n<<=1;initrev(n);
ntt(c,n,0);ntt(b,n,0);
for(int i=0;i<n;i++)
b[i]=(2ll*b[i]%md-c[i]*b[i]%md*b[i]%md+md)%md;
ntt(b,n,1);n>>=1;
for(int i=n;i<n*2;i++)b[i]=0;
}
inline void cln(ll *a,ll *b,int n)
{
static ll c[N],d[N],l;
memset(c,0,sizeof(c));
memset(d,0,sizeof(d));
for(int i=0;i<n;i++)
c[i]=a[i];
for(l=1;l<=n;l<<=1);
cinv(c,d,l);
for(int i=0;i<n;i++)
c[i]=c[i+1]*(i+1)%md;
l<<=1;initrev(l);
ntt(c,l,0);ntt(d,l,0);
for(int i=0;i<l;i++)
d[i]=c[i]*d[i]%md;
ntt(d,l,1);
for(int i=1;i<n;i++)
b[i]=d[i-1]*qpow(i,md-2)%md;
b[0]=0;
}
inline void init()
{
fac[0]=1;
for(ll i=1;i<N;i++)
fac[i]=fac[i-1]*i%md;
inv[N-1]=qpow(fac[N-1],md-2);
for(ll i=N-1;i>=1;i--)
inv[i-1]=inv[i]*i%md;
for(ll i=0;i<M;i++)
h[i]=qpow(2,i*(i-1)/2)*inv[i]%md;
cln(h,f,M);
for(ll i=1;i<=M;i++)
f[i]=f[i]*fac[i]%md*inv[i-1]%md;
g[0][0]=1;
for(int i=0;i<K-1;i++)
{
for(int j=1;j<M;j++)
g[i][j]=g[i][j]*fac[j-1]%md*inv[j]%md;
mul(g[i],M,h,M,t[i]);
mul(g[i],M,f,M,g[i+1]);
}
s[0][0]=1;
for(int i=1;i<K;i++)
{
s[i][0]=0;s[i][i]=1;
for(int j=1;j<=i;j++)
s[i][j]=(j*s[i-1][j]%md+s[i-1][j-1])%md;
}
}
inline int mina()
{
scanf("%d%d",&n,&k);
if(k==0)return puts("1"),0;
ll ans=0,all=qpow(2,(ll)n*(n-1ll)/2ll);
for(int i=1;i<=k;i++)
(ans+=s[k][i]*fac[i]%md*t[i][n]%md)%=md;
printf("%lld
",ans*fac[n]%md*qpow(all,md-2)%md);
}
int main()
{
init();
int T;scanf("%d",&T);
while(T--)mina();
return 0;
}