24.10.15

KinNa-Sky / 2024-10-18 / 原文

谁家好人往 NOIp 模拟赛里塞 CF *3500 啊。

A

考察 $x$ 与 $< x$ 的点的连边。

\[\begin{aligned} &x | (y + n)\\ &kx = y + n\\ &y = kx - n\\ &\because 0<y<x \le n\\ &\therefore y 只有 1 个\\ \Rightarrow &k = \left\lceil\frac{n}{x}\right\rceil, y = \left\lceil\frac{n}{x}\right\rceil x -n \end{aligned} \]

也就是构成了森林的结构，求两个点的距离直接暴力跳父亲找 LCA，由于保证数据随机所以每次期望减半。

B

$m$ 个点去匹配考虑给 $m$ 全排列，前面的点的所有边权严格大于后面的点，然后每个点从前往后匹配。

然后以 $O(m!m^2)$ 的复杂度解决了，有点极限但能过。

C

/**
 * 拆贡献, 每个点集选一个贡献 (+val[i]) 剩下的不贡献 (+1)
 * 
 * "取" 指放到点集里
 * f[x][a][b] 表示 x 子树内 有 a 个未取且不贡献(1), 有 b 个点未取且贡献(val) 的权值和
 * g,h 第一维 表示根 是否钦定为 lca, 是否贡献 的权值和
 * 0 : 00
 * 1 : 01
 * 2 : 10
 * 3 : 11
 * 4 : 维护 2 的转移, 存子树内不贡献点各方案权值和
 */

方程：

memset(g, 0, sizeof g);
g[0][0][0] = 1; g[1][0][0] = val[x];
g[2][0][0] = 0; g[3][0][0] = val[x];
g[4][0][0] = 1;
redg(i, e, x, y) if (y != fa) {
	memcpy(h, g, sizeof h);
	memset(g, 0, sizeof g);
	rep(a, 0, siz[x]) rep(b, 0, siz[x] - a)
		rep(c, 0, siz[y]) rep(d, 0, siz[y] - c) {
			// 选不了点
			(g[0][a + c][b + d] += h[0][a][b] * f[y][c][d] % mod) %= mod;
			(g[1][a + c][b + d] += h[1][a][b] * f[y][c][d] % mod) %= mod;

			// 不选点
			(g[2][a + c][b + d] += h[2][a][b] * f[y][c][d] % mod) %= mod;
			// 选不贡献点
			if (c) (g[2][a + c - 1][b + d] += h[2][a][b] * f[y][c][d] % mod * c % mod) %= mod;
			// 选贡献点 (每个集合选一个点贡献, 从 4 转移)
			if (d) (g[2][a + c][b + d - 1] += h[4][a][b] * f[y][c][d] % mod * d % mod) %= mod;

			// 不选点
			(g[3][a + c][b + d] += h[3][a][b] * f[y][c][d] % mod) %= mod;
			// 选不贡献点
			if (c) (g[3][a + c - 1][b + d] += h[3][a][b] * f[y][c][d] % mod * c % mod) %= mod;

			// 不选点
			(g[4][a + c][b + d] += h[4][a][b] * f[y][c][d] % mod) %= mod;
			// 选不贡献点
			if (c) (g[4][a + c - 1][b + d] += h[4][a][b] * f[y][c][d] % mod * c % mod) %= mod;
		}
	siz[x] += siz[y];
}
rep(a, 0, siz[x]) rep(b, 0, siz[x])
	(f[x][a + 1][b] += g[0][a][b]) %= mod,
	(f[x][a][b + 1] += g[1][a][b]) %= mod,
	(f[x][a][b] += g[2][a][b]) %= mod,
	(f[x][a][b] += g[3][a][b]) %= mod;