\(\text{Link}\)
题意
给定一张 \(n\) 个点和 \(m\) 条边，对于 \(\forall i\in[1,n)\) 求出选择图中 \(i\) 条边的方案数，使得选出的边不成环。对 \(998244353\) 取模。
\(n\le 20\)，\(m\le 500\)。
思路
很明显是集合幂级数题目且不是很直接，直接考虑逐点牛顿迭代。
首先求出 \(F_S\) 表示点集 \(S\) 的生成树个数，和边双连通-连通变换做法类似，按照两端点编号的最大值的顺序进行加边，枚举 \(i\) 表示允许加入两端点编号最大值为 \(i\) 的边即可。每个 \(i\) 都需要一次大小为 \(2^i\) 的集合幂级数 \(\exp\) 进行合并，时间复杂度 \(O(2^nn^2)\)。
接下来是考虑合并若干森林。如果选出了 \(i\) 条边，那么就会形成 \(n-i-1\) 个连通块，对应方案数即为 \([x^U]F^{n-i-1}\)，需要对 \(\forall i\in[1,n)\) 求出 \([x^U]F^i\)，这与多项式复合集合幂级数的形式是一致的。但是不同的是，P10461 需要对每个 \(S\) 求出 \([x^S]\sum_i a_iF^i\)，而此处需要求出每一个 \([x^U]F^i\) 的值。
本题实际上相当于多起点单终点的 DP，P10461 需要求出的是从唯一起点到每个终点的路径数分别有多少路径（虽然实际上为了优化时间复杂度，状态被翻转为多起点多终点，但是只需要求任一起点到每个终点的路径数之和），而本题需要求出每一个起点到唯一终点分别有多少路径。这种情况我们要翻转转移路径，或者说称其为转置原理。
依然逐点牛顿迭代，但我们将流程翻转。从大到小枚举 \(i\)，删去方案中 \(\max S=i\) 的连通块 \(S\)。
记 \(H_{k,S}\) 表示已经删除了 \(k\) 次，剩余的点集为 \(S\) 的方案数，另记集合幂级数 \(F'_S\)，在 \(\max S=i\) 时等于 \(F_S\)，其余时刻等于 \(0\)。注意此时 \(k\) 的上界为 \(n-i\)，且集合幂级数 \(H_k,F'\) 的有效长度均为 \(2^i\)。
那么再从大到小枚举 \(k\)，将 \(H_{k}\) 与 \(F'\) 做子集差卷积的结果加给 \(H_{k+1}\)。其中子集差卷积即为求出：
类似形式幂级数的差卷积，翻转 \(F,H\) 即可。
总时间复杂度为 \(\sum_i2^ii^2(n-i)=O(2^nn^2)\)，可以通过。
:::info[核心代码]
int n,m,a[N][N],u,F[S],G[N],R[N][S],T1[S],T2[S];
inline void CalcTree(){F[0]=1;for(int i=0;i<n;i++){Poly::init(1<<i);for(int s=0;s<(1<<i);s++){if(s){int lb=__lg(s&-s);T2[s]=T2[s^(1<<lb)]+a[i][lb];}T1[s]=1ll*F[s]*T2[s]%mod;}Poly::Exp(T1,T1);for(int s=0;s<(1<<i);s++)F[s^(1<<i)]=T1[s]; }
}
inline void CompR(){R[0][u-1]=1;for(int i=n-1;i>=0;i--){Poly::init(1<<i);for(int j=0;j<(1<<i);j++)T1[j]=F[j^(1<<i)];for(int j=n-i-1;j>=0;j--){for(int k=0;k<(1<<i);k++)T2[k]=R[j][k^(1<<i)];Poly::MulR(T2,T1,T2);for(int k=0;k<(1<<i);k++)inc(R[j+1][k],T2[k]);}}for(int i=0;i<=n;i++)G[i]=R[i][0];
}
int main(){n=read(),m=read(),u=1<<n;while(m--){int u=read()-1,v=read()-1;a[u][v]++,a[v][u]++;}Prefix(u);CalcTree(),CompR();for(int i=1;i<n;i++)write(1ll*G[n-i]*fac[i]%mod),putc('\n');flush();
}
:::