Luogu 月赛 F P6789 寒妖王 [* easy]
给定 (n) 个点 (m) 条边的图，第 (i) 条边的权值为 (w_i)，每条边有 (frac{1}{2}) 的概率被保留，求最后这张图的最大基环树森林的边权和。
Solution
(mathcal O(2^mcdot malpha(n))) 是显然的。
类比一下 Kruskal 求 MST 就会做了。
考虑优化，我们不妨考虑判定一条边什么情况下不会被加入答案，等价于仅考虑边权大于他的边，有他连接的两个点：
- 连通，且此时不为树。
- 不连通，此时这两个点分别在一个基环树上。
第一类贡献很简单，我们统计仅保留这些边时点集 (S) 的生成树的数量。这个可以枚举子集 (Tsubseteq S)，然后计算一棵生成树，不难发现每棵生成树会被计算 (|S|-1) 次，除掉即可。
统计 (T o Tland S) 中的边数通过 (cnt_S-cnt_T-cnt_{Tland S}) 来计算，这样复杂度为 (mathcal O(mcdot 3^n))，需要适当减枝，比如点集 (S) 的边数小于 (|S|-1) 时就直接 out
接下来考虑统计第二类贡献。
不难发现第二类贡献等价于点集 (A) 和点集 (B) 满足 (xin A,yin B) 且 (A) 是联通图不是生成树，(B) 是联通图不是树。
枚举 (A,B) 的总量是 (3^n) 的，这样只需要预处理联通图计数，经典的容斥手段可以做到 (mathcal O(3^n))
最后，我们在 (mathcal O(m3^n)) 的复杂度解决了此问题。
- 预处理 (cnt) 数组我是用高维前缀和算的。
(Code:)
#include<bits/stdc++.h>
using namespace std ;
#define Next( i, x ) for( register int i = head[x]; i; i = e[i].next )
#define rep( i, s, t ) for( register int i = (s); i <= (t); ++ i )
#define drep( i, s, t ) for( register int i = (t); i >= (s); -- i )
#define re register
#define int long long
int gi() {
char cc = getchar() ; int cn = 0, flus = 1 ;
while( cc < '0' || cc > '9' ) { if( cc == '-' ) flus = - flus ; cc = getchar() ; }
while( cc >= '0' && cc <= '9' ) cn = cn * 10 + cc - '0', cc = getchar() ;
return cn * flus ;
}
const int P = 998244353 ;
const int N = (1 << 16) + 5 ;
int n, m, limit, bit[N], ip[N], fac[70], iv[35], f[N], g[N], cnt[N], Ans ;
struct E {
int u, v, w ;
} e[100] ;
bool cmp(E x, E y) { return x.w > y.w ; }
int fpow(int x, int k) {
int ans = 1, base = x ;
while(k) {
if(k & 1) ans = 1ll * ans * base % P ;
base = 1ll * base * base % P, k >>= 1 ;
} return ans ;
}
void inc(int &x, int y) { ((x += y) >= P) && (x -= P) ; }
void solve(int x) {
memset( cnt, 0, sizeof(cnt) ), memset( f, 0, sizeof(f) ), memset( g, 0, sizeof(g) ) ;
rep( i, 1, x - 1 ) ++ cnt[(1 << e[i].u) | (1 << e[i].v)] ;
for(re int k = 1; k <= limit; k <<= 1 )
rep( i, 0, limit ) if(i & k) cnt[i] += cnt[i ^ k] ;
rep( S, 1, limit ) {
if( bit[S] == 1 ) { f[S] = g[S] = 1 ; continue ; }
if( cnt[S] < bit[S] - 1 ) { f[S] = 0 ; g[S] = 0 ; continue ; }
int w = (1 << ip[S]), z = S ^ w ; f[S] = 0, g[S] = fac[cnt[S]] ;
for(re int i = z; i; i = (i - 1) & z) {
int u = i ^ S, t = cnt[S] - cnt[i] - cnt[u] ;
f[S] = (f[S] + 1ll * f[i] * f[u] % P * t ) ;
g[S] = (g[S] - g[u] * fac[cnt[i]] % P) ;
}
f[S] %= P, g[S] = (g[S] % P + P) % P ;
f[S] = f[S] * iv[bit[S] - 1] % P ;
}
int ans = 0, u = (1 << e[x].u), v = (1 << e[x].v) ;
rep( S, 1, limit ) g[S] = (g[S] % P - f[S] % P + P) % P ;
rep( S, 1, limit ) {
if( (!(S & u)) || (!(S & v)) ) continue ;
int d = g[S] ; d = d * fac[cnt[limit ^ S]] % P ;
ans = (ans + d) % P ;
//S 联通且不为树，枚举 S，外部任意
}
rep( A, 1, limit ) {
if( (!(A & u)) || (A & v) ) continue ;
int T = A ^ limit ;
for(re int B = T; B; B = (B - 1) & T) {
if( !(B & v) ) continue ;
ans = (ans + 1ll * g[A] * g[B] % P * fac[cnt[limit ^ A ^ B]] % P) % P ;
}
}
int ffv = (P + 1) / 2 ;
ans = ans * fpow( fac[x], P - 2 ) % P, ans = (ffv - ans + P) % P ;
Ans = (Ans + ans * e[x].w) % P ;
}
signed main()
{
n = gi(), m = gi() ;
rep( i, 1, m )
e[i].u = gi() - 1, e[i].v = gi() - 1, e[i].w = gi() ;
sort(e + 1, e + m + 1, cmp), iv[0] = fac[0] = 1 ;
rep( i, 1, n ) iv[i] = fpow(i, P - 2) ;
rep( i, 1, m ) fac[i] = fac[i - 1] * 2 % P ;
limit = (1 << n) - 1 ;
rep( i, 1, limit ) {
bit[i] = __builtin_popcountll(i) ;
rep( j, 0, n - 1 ) if((1 << j) & i) { ip[i] = j ; break ; }
}
rep( i, 1, m ) solve(i) ;
cout << (long long)Ans << endl ;
return 0 ;
}