2022牛客多校#6 C. Forest

给定 n ( 1 ≤ n ≤ 16 ) n(1 leq n leq 16) n(1≤n≤16) 个点 m ( 0 ≤ m ≤ 100 ) m(0 leq m leq 100) m(0≤m≤100) 条正边权的无向简单图，求每个生成子图的最小生成森林的权值和，答案对 998244353 998244353 998244353 取模。

定义点集 V V V ，边集 E E E 的图 G G G 的最小生成森林为：

• 最小生成森林的边集 S ⊆ E S subseteq E S⊆E 。
• 任意两个节点的连通性不变
• S S S 为满足以上条件的最小权值。

图 G G G 的生成子图为具有点集 V V V 和边集为 E E E 的子集所构成的图。

类似题目 P6789 。

单独考虑按边权值从小到大枚举每条边的贡献，边权值第 i i i 小的边为 e i = ( u i , v i , w i ) e_i=(u_i,v_i,w_i) ei​=(ui​,vi​,wi​) 。
由于求所有方案的总权值和，因此边权值相同的边任意排序后不影响结果。

定理：

• 一条边在生成子图的最小生成森林中，当且仅当该子图中其他权值更小的点不能使得两端联通。

对于边 e i = ( u i , v i , w i ) e_i=(u_i,v_i,w_i) ei​=(ui​,vi​,wi​) ，求有多少生成子图的最小生成森林包含该边。

边编号在 [ i + 1 , m ] [i+1,m] [i+1,m] 范围内的边，不影响 e i e_i ei​ 的选取，方案数为 2 m − 1 − i 2^{m-1-i} 2m−1−i 。

考虑边编号在 [ 1 ， i − 1 ] [1，i-1] [1，i−1] 范围内的边。
设边编号在 [ 1 , i − 1 ] [1,i-1] [1,i−1] 范围内，且端点均在点集 S S S 内的边数为 C n t i − 1 ( S ) Cnt_{i-1}(S) Cnti−1​(S) ，有转移式
C n t i ( S ) = [ u i ∈ S & v i ∈ S ] + C n t i − 1 ( S ) Cnt_{i}(S)=[u_iin S&v_i in S]+Cnt_{i-1}(S) Cnti​(S)=[ui​∈S&vi​∈S]+Cnti−1​(S)

设边编号在 [ 1 , i − 1 ] [1,i-1] [1,i−1] 范围的边构成连通块 S S S ，则

1. 两端在 S S S 外的边，可以任意选取。方案数为 2 C n t i − 1 ( V − S ) 2^{Cnt_{i-1}(V-S)} 2Cnti−1​(V−S) ；
2. 只有一段在 S S S 内的边，均不能选取，否则连通块就不是 S S S 了。方案数为 1 1 1 ；
3. 两端都在 S S S 内的边，有一部分需要被选取使得构成连通块 S S S 。设方案数为 f i − 1 ( S ) f_{i-1}(S) fi−1​(S) ；

考虑计算 f i − 1 ( S ) f_{i-1}(S) fi−1​(S) ，等于总方案数-至少有两个连通块的方案数。
可以直接计算，枚举 S S S 中包含编号最小的节点的连通块 T T T ，则剩余部分为 S − T S-T S−T ，有
f i − 1 ( S ) = 2 C n t i − 1 ( S ) − ∑ T ⊂ S , l o w b i t ( S ) = l o w b i t ( T ) f i − 1 ( T ) ⋅ 2 C n t i − 1 ( S − T ) f_{i-1}(S)=2^{Cnt_{i-1}(S)}-sum_{T subset S,lowbit(S)=lowbit(T)}{f_{i-1}(T)cdot 2^{Cnt_{i-1}(S-T)}} fi−1​(S)=2Cnti−1​(S)−T⊂S,lowbit(S)=lowbit(T)∑​fi−1​(T)⋅2Cnti−1​(S−T)

上式的复杂度为 O ( 3 n ) O(3^n) O(3n) ，搭配枚举 m m m ，复杂度为 O ( 3 n m ) O(3^n m) O(3nm) ，约 4e9 ，勉强可以计算出结果。

边 e i e_i ei​ 的贡献为
W i = w i × ( 2 m − 1 − 2 m − i − 1 × ∑ S ⊆ V , u i ∈ S , v i ∈ S 2 C n t i − 1 ( V − S ) f i − 1 ( S ) ) W_i=w_itimes(2^{m-1}-2^{m-i-1} times sum_{Ssubseteq V,u_i in S,v_i in S}{2^{Cnt_{i-1}(V-S)}f_{i-1}(S)}) Wi​=wi​×(2m−1−2m−i−1×S⊆V,ui​∈S,vi​∈S∑​2Cnti−1​(V−S)fi−1​(S))

也可以考虑加入 e i e_i ei​ 边，从 f i − 1 ( S ) f_{i-1}(S) fi−1​(S) 递推到 f i ( S ) f_{i}(S) fi​(S) ，有
f i ( S ) = { 2 f i − 1 ( S ) + ∑ T ⊂ S , u i ∉ T , v i ∉ T f i − 1 ( S − T − v i ) ⋅ f i − 1 ( T + u i ) u i ∈ S , v i ∈ S f i − 1 ( S ) o t h e r s f_i(S)=begin{cases} 2f_{i-1}(S)+sum_{Tsubset S,u_i notin T, v_i notin T}f_{i-1}(S-T-{v_i})cdot f_{i-1}(T+{u_i}) & u_i in S,v_i in S\ f_{i-1}(S) & others end{cases} fi​(S)={2fi−1​(S)+∑T⊂S,ui​∈/T,vi​∈/T​fi−1​(S−T−vi​)⋅fi−1​(T+ui​)fi−1​(S)​ui​∈S,vi​∈Sothers​

总复杂度 O ( m ⋅ 3 n − 2 ) O(mcdot 3^{n-2}) O(m⋅3n−2) ，约4e8。

来自杭电6队

#include
#define ll long long
using namespace std;
const int N=20;
const int mod=998244353;
struct node{
	int u,v,s;
};
vectorw;
bool operator<(const node&x,const node&y){
	return x.sreturn x+y>=mod?x+y-mod:x+y;}
int dec(int x,int y){return x-y<0?x-y+mod:x-y;}
int mul(int x,int y){return (ll)x*y%mod;}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++){
		for (int j=1;j<=n;j++) scanf("%d",&a[i][j]);
	}
	for (int i=1;i<=n;i++) 
		for (int j=i+1;j<=n;j++)if (a[i][j]){
			node t; t.u=i; t.v=j; t.s=a[i][j];
			w.push_back(t);
		}
	sort(w.begin(),w.end());
	for (int i=1;i<=n;i++) f[1<<(i-1)]=1;
	fac[0]=1;
	for (int i=1;i<=500;i++) fac[i]=mul(fac[i-1],2);
	int m=(1<
		int u=w[i].u,v=w[i].v; u--;v--;
		int t=(1<
			g[j|(1<
		if ((j&(1<