【ABC253EX】We Love Forest
Description
给出一张\(n\)个点\(m\)条边的无向图
会进行\(n-1\)次操作，每次从\(m\)条边中随机选一条加入图\(G\)
对于\(i=1,2\cdots n-1\)，求进行\(i\)次操作后\(G\)为森林的概率
对\(998244353\)取模
Input
第一行两个数\(n,m\)
然后\(m\)行读入边
Output
一共\(n-1\)行表示答案
Sample Input
3 2
1 2
2 3
Sample Output
1
499122177
Data Constraint
\(1\le n\le 14\)
Solution
这是对\(O(n^22^n)\)爆标做法的详细阐述：
第一步是计算每个子集的生成树个数
考虑逐点牛顿迭代法
假设要加入\(n\)号点，那么删去\(n\)后形成了若干联通块
我们钦定\(n\)为根，然后可以计算出当前所有子集与其连边数
然后让子集乘上连边数，再做集合幂exp
第二步可以转化成对所有\(k=1,2\cdots n-1\)求出有\(k\)颗树的方案数
我们可以一般化这个问题：
\(a_i=\sum_{S\subset U}b_S[x^S]\frac{f^i}{i!}\)
显然可以看成是若干初等矩阵的变换
于是转置后就是\(b_S=[x^S]\sum_{i\ge 0}a_i\frac{f^i}{i!}\)
这是一个集合幂级数复合问题
对于复合问题\(F=f(G)\)，考虑将\(\frac{\partial}{\partial x_n}\)作用于两边
于是有\([x_n^1]F=([x_{n-1}^0]f'(G))([x_n^1]G)\)，同时\([x_n^0]F=[x_n^1]f(G)\)
显然可以递归下去
观察过程：
1.\(h_{0,i}=f_i\)
2.对于\(k=1,2\cdots n\)，\(j=0,1\cdots n-k\)
有\(h_{k,j}[0\cdots2^{k-1}-1]=h_{k-1,j}\)，\(h_{k,j}[2^{k-1}\cdots2^{k}-1]=h_{k-1,j+1}*g[2^{k-1}\cdots 2^k-1]\)
答案就是\(h_{n,0}[0\cdots 2^{n}-1]\)
现在将问题转置，于是有
1.\(h_{n,0}[0\cdots 2^n-1]=b[0\cdots 2^n-1]\)
2.对于\(k=n,n-1\cdots 1\)，\(j=n-k,n-k-1\cdots 0\)
有\(h_{k-1,j+1}+=h_{k,j}[2^{k-1}\cdots2^{k}-1]*g[2^{k-1}\cdots 2^k-1]\)，\(h_{k-1,j}+=h_{k,j}[0\cdots2^{k-1}-1]\)
最后\(a_i=h_{0,i}\)
要注意的是，这里的乘法为转置乘法
对于集合幂级数的转置乘法，首先我们要将FMT改为转置形式，记为TFMT和TIFMT
然后对于形式幂级数的乘法，就是经典的差卷积
对于上面的\(h*g\)，算法可以写为：
1.对\(h\)做TIFMT（这里的\(g\)应该看做常数，所以\(g\)只需正常做FMT）
2.将\(h\)和\(g\)做差卷积，记录在\(h'\)中
3.对\(h'\)做TFMT
复杂度：
对于生成树计数，其和式为\(\sum_i2^ii^2\)，即\(O(n^22^n)\)
对于第二部分，转置前后复杂度不变，都是\(\sum_i(n-i)2^ii^2\)，经EI证明为\(O(n^22^n)\)
Code
#include<bits/stdc++.h>
using namespace std;
#define F(i,a,b) for(int i=a;i<=b;i++)
#define Fd(i,a,b) for(int i=a;i>=b;i--)
#define ull unsigned long long
#define mo 998244353
#define N 15
int n,m,e[N][N],f[1<<N],g[1<<N][N],res[1<<N],inv[N],ifac[N],fac[N];
int count(int x){return x?count(x>>1)+(x&1):0;}
int mi(int x,int y){
if(y==1)return x;
return y&1?1ll*x*mi(1ll*x*x%mo,y/2)%mo:mi(1ll*x*x%mo,y/2);
}
int mod(int x){return x>=mo?x-mo:x;}
void FMT(int A[][N],int lg,int sz,int x){
F(i,0,lg-1) for(int j=0;j<sz;j+=(1<<i+1)){
F(k,j,j+(1<<i)-1) F(d,0,lg)A[k|(1<<i)][d]=mod(A[k|(1<<i)][d]+(x==1?A[k][d]:mo-A[k][d]));
}
}
void TFMT(int A[][N],int lg,int sz,int x){
F(i,0,lg-1) for(int j=0;j<sz;j+=(1<<i+1)){
F(k,j,j+(1<<i)-1) F(d,0,lg)A[k][d]=mod(A[k][d]+(x==1?A[k|(1<<i)][d]:mo-A[k|(1<<i)][d]));
}
}
void Exp_GF(int*A,int lg){
F(i,0,lg)res[i]=0;
res[0]=1;
F(i,1,lg){
ull s=0;
F(j,1,i)s+=1ull*res[i-j]*A[j]%mo*j;
res[i]=1ll*(s%mo)*inv[i]%mo;
}
F(i,0,lg)A[i]=res[i];
}
void Exp(int lg,int sz){
FMT(g,lg,sz,1);
F(i,0,sz-1)Exp_GF(g[i],lg);
FMT(g,lg,sz,-1);
}
void solve(){
f[0]=1;
F(i,0,n-1){
F(j,0,(1<<i)-1) F(k,0,i)g[j][k]=0;
F(j,0,(1<<i)-1){
int w=0;
F(k,1,n)if(j&(1<<k-1))w+=e[i+1][k];
g[j][count(j)]=1ll*f[j]*w%mo;
}
Exp(i,1<<i);
F(j,1<<i,(1<<i+1)-1)f[j]=g[j^(1<<i)][count(j)-1];
}
}
int ans[N],h[N][1<<N],pre[1<<N][N];
void Conv(int*A,int*B,int lg,int sz){
static int tmp[1<<N][N];
F(i,0,sz-1) F(j,0,lg)tmp[i][j]=0;
F(i,0,sz-1)tmp[i][count(i)]=A[i];
TFMT(tmp,lg,sz,-1);
F(i,0,sz-1) F(j,0,lg){
ull s=0;
F(k,0,lg-j)s+=1ull*tmp[i][j+k]*pre[i][k];
tmp[i][j]=s%mo;
}
TFMT(tmp,lg,sz,1);
F(i,0,sz-1)B[i]=mod(B[i]+tmp[i][count(i)]);
}
void Composite(){
h[0][(1<<n)-1]=1;
memset(g,0,sizeof(g));
F(i,0,(1<<n)-1)g[i][count(i)]=f[i];
Fd(i,n,1){
F(j,0,(1<<i-1)-1) F(k,0,i-1)pre[j][k]=g[j|(1<<i-1)][k+1];
FMT(pre,i-1,1<<i-1,1);
Fd(j,n-i,0)Conv(h[j]+(1<<i-1),h[j+1],i-1,1<<i-1);
}
F(i,0,n)ans[i]=h[i][0];
}
int main(){
scanf("%d%d",&n,&m);
ifac[0]=fac[0]=1;
F(i,1,n){
inv[i]=mi(i,mo-2);
ifac[i]=1ll*ifac[i-1]*inv[i]%mo;
fac[i]=1ll*fac[i-1]*i%mo;
}
F(i,1,m){
int u,v;
scanf("%d%d",&u,&v);
e[u][v]++;
e[v][u]++;
}
solve();
f[0]=0;
Composite();
int im=mi(m,mo-2),pr=1;
F(i,1,n-1){
pr=1ll*pr*im%mo;
printf("%d\n",1ll*ans[n-i]*pr%mo*fac[i]%mo);
}
return 0;
}