CF1067E Random Forest Rank

标签：ch int CF1067E Random while read 1ll Forest mod

非常神秘题。

考虑 \(\operatorname{rank} A = n\) 当且仅当 \(\det A \neq 0\)，我们把 \(\det A\) 写下来：

\[\sum_{p} (-1)^{\pi(p)} \prod_{i=1}^n A_{i,p_i} \]

考虑这是个森林的邻接矩阵，排列 \(p\) 有贡献当且仅当 \(p\) 仅包含大小等于 \(2\) 的环。放在树上来看恰好对应了一组完美匹配。于是 \(\operatorname{rank} A=\) 最大匹配大小 \(\times 2\)。

直接考虑拆贡献 dp，设 \(f_i\) 表示 \(i\) 与一个儿子匹配的概率，非常好计算。

#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5, mod = 998244353;

inline int read() {
	register int s = 0, f = 1; register char ch = getchar();
	while (!isdigit(ch)) f = (ch == '-' ? -1 : 1), ch = getchar();
	while (isdigit(ch)) s = (s * 10) + (ch & 15), ch = getchar();
	return s * f;
}

inline int power(int a, int b) {
	int t = 1, y = a, k = b;
	while (k) {
		if (k & 1) t = (1ll * t * y) % mod;
		y = (1ll * y * y) % mod; k >>= 1;
	} return t;
}

struct edge {
	int head, to, nxt;
} ed[N << 1];

int en = 0;

inline void addedge(int from, int to) {
	ed[++en].to = to; ed[en].nxt = ed[from].head; ed[from].head = en;
}

int f[N];

const int inv2 = power(2, mod - 2);

int ans = 0, n;

inline void dfs(int now, int fa) {
	f[now] = 1;
	for (int i = ed[now].head; i; i = ed[i].nxt) {
		int v = ed[i].to;
		if (v == fa) continue;
		dfs(v, now);
		f[now] = 1ll * (1 + f[ed[i].to]) * (1ll * f[now] * inv2 % mod) % mod;
	} ans += (f[now] = (1 + mod - f[now])) % mod;
	if (ans >= mod) ans -= mod;
}

int main() {
	n = read();
	for (int i = 1, u, v; i < n; ++i) {
		u = read(); v = read();
		addedge(u, v); addedge(v, u);
	} dfs(1, 0);
	printf("%d\n", 1ll * ans * power(2, n) % mod);
	return 0;
}

标签：ch,int,CF1067E,Random,while,read,1ll,Forest,mod
From： https://www.cnblogs.com/wwlwakioi/p/17206143.html