初来乍到，4h20min的题我打了2h，成功垫底，恭喜我自己

$\text{score：20 + 0 + 0 = 20 rk：26/27}$

Problen A

题目描述

题解

看他们都会写。。这种比较复杂的容斥我几乎都没写过。。

前置知识：高维前缀和

举个例子，对比如现在要求解 $\sum\limits_{s = 0}^{2^n - 1}\sum\limits_{j \in s} a_j$（此处 $\in$ 是二进制表示下的意义），直接枚举子集是 $O (3^n)$ 的，那么高维前缀和可以优化到 $O (n2^n)$

考虑低位前缀和，比如三位，我们是不是可以这么写

1
2
3
4
5
6
7
8
9
10
11
12
for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= n; j ++)
        for (int k = 1; k <= n; k ++)
            a[i][j][k] += a[i - 1][j][k]
for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= n; j ++)
        for (int k = 1; k <= n; k ++)
            a[i][j][k] += a[i][j - 1][k]
for (int i = 1; i <= n; i ++)
    for (int j = 1; j <= n; j ++)
        for (int k = 1; k <= n; k ++)
            a[i][j][k] += a[i][j][k - 1]

就是对每一维分别求前缀和，那么高维前缀和也是这个思想，即 $f_{s \oplus (1 << j)} \rightarrow f_s$

1
2
3
4
5
int limit = (1 << n) - 1;
for (int j = 1; j <= n; j ++)
    for (int s = 0; s <= limit; s ++)
        if (s & (1 << (j - 1)))
            f[s] += f[s ^ (1 << (j - 1))];

回到正题

令 $|s|$ 表示 $s$ 的二进制表示下 $1$ 的个数

设 $g_s$ 表示构成最终状态 $s$ 的方案数，$f_s$ 表示状态 $s$ 二进制表示中的为 $0$ 位的卡片至少不存在于最终收藏的方案数，那么容斥一下有
$$
g_s = \sum\limits_{j \in s} f_j \times (-1)^{|s - j|}（根据多出来的 0 的个数进行容斥）
$$
那么现在考虑求 $f_s$

先考虑暴力计算，枚举 $s$，将每一轮满足相位置是零的组合的概率加起来为 $sum_i$，最后则有 $f_s = \prod sum_i$，这样显然会 $T$

对每一轮，可能满足的组合的组合共有 $2^k$ 种，现在考虑这 $2^k$ 种可能性分别都贡献到哪儿了

设对于当前取 $2^k$ 种状态中的一种所表示出的二进制状态为 $s$，该种组合的组合对应的卡片集合 $card_s$，概率和 $p_s$，那么很明显它可以贡献到的就是 $card_s$ 的超集，当然由于它子集也会贡献到那些超集，故还需容斥掉，设它使超集需要乘上数 $L_{card_s}$
$$
L_{card_s} = \prod\limits_{j \in s} p_j^{(- 1)^{|s - j|}}
$$
之后就可以通过计算子集给 $f_s$ 的贡献直接求出 $f_s$ 了

需要注意的是，当 $j$ 取空集的时候，$p_j = 0$，而 $p_j$ 又有可能被作为除数，故此时需要开一个数组计算到此为止究竟乘和除以了多少个零，若最终乘的次数多，则直接将 $f_s$ 赋零

最后一遍容斥求出 $g_s$

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>

#define MOD 1000000007

using namespace std;

typedef long long LL;

const int MAXM = 1 << 20;
const int MAXK = 10 + 5;
const int KTRS = 1 << 10;

inline int lowbit (int x) { return x & (- x); }
int mp[MAXM]= {0}, pcnt[MAXM]= {0};
LL power (LL x, int p) {
	LL cnt = 1;
	while (p) {
		if (p & 1) cnt = cnt * x % MOD;
		x = x * x % MOD, p >>= 1;
	}
	return cnt;
}

int N, M;
int a[MAXK], p[MAXK];

int suma[KTRS]= {0};
LL sump[KTRS]= {0}, undp[KTRS]= {0};

int zocnt[MAXM]= {0};
LL f[MAXM]= {0};

LL g[MAXM]= {0};

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	N = getnum (), M = getnum ();
	int lim = (1 << M) - 1;
	for (int i = 2; i <= lim; i ++) mp[i] = mp[i >> 1] + 1;
	for (int i = 1; i <= lim; i ++) pcnt[i] = pcnt[i >> 1] + (i & 1);
	for (int i = 0; i <= lim; i ++) f[i] = 1;
	for (int i = 1; i <= N; i ++) {
		int K = getnum (), d = 0;
		for (int j = 0; j < K; j ++) {
			a[j] = getnum (), p[j] = getnum ();
			d += p[j];
		}
		int poe = power (1ll * d, MOD - 2);
		for (int j = 0; j < K; j ++) p[j] = 1ll * p[j] * poe % MOD;
		int lik = (1 << K) - 1;
		sump[0] = undp[0] = 0;
		for (int j = 1; j <= lik; j ++) {
			suma[j] = suma[j ^ lowbit (j)] | a[mp[lowbit (j)]];
			sump[j] = (sump[j ^ lowbit (j)] + p[mp[lowbit (j)]]) % MOD;
			undp[j] = power (sump[j], MOD - 2);
		}
		sump[0] = undp[0] = 1;
		for (int j = 0; j < K; j ++) {
			int l = 1 << j;
			for (int k = 0; k <= lik; k ++)
				if (k & l) {
					sump[k] = sump[k] * undp[k ^ l] % MOD;
					undp[k] = undp[k] * sump[k ^ l] % MOD;
				}
		}
		zocnt[0] ++;
		for (int j = 1; j <= lik; j ++) {
			if (pcnt[j] & 1) zocnt[suma[j]] --;
			else zocnt[suma[j]] ++;
			f[suma[j]] = f[suma[j]] * sump[j] % MOD;
		}
	}
	for (int i = 0; i < M; i ++) {
		int l = 1 << i;
		for (int j = 0; j <= lim; j ++)
			if (j & l) {
				f[j] = f[j] * f[j ^ l] % MOD;
				zocnt[j] += zocnt[j ^ l];
			}
	}
	for (int i = 0; i <= lim; i ++) {
		if (zocnt[i] > 0) g[i] = 0;
		else g[i] = f[i];
	}
	for (int i = 0; i < M; i ++) {
		int l = 1 << i;
		for (int j = 0; j <= lim; j ++)
			if (j & l) g[j] = (g[j] - g[j ^ l] + MOD) % MOD; // 注意这里使容斥，某个g[j]被减两次则变成加
	}
	LL ans = 0;
	for (int j = 0; j <= lim; j ++) ans ^= g[j];
	cout << ans << endl;

	return 0;
}

Problem B

问题描述

给定一个 $n$ 个点 $m$ 条边的连通无向图，边上有边权，求该无向图的最小直径生成树，其具有最小的直径

数据范围

$1 \le n \le 500, ~ n - 1 \le m \le \frac{n(n - 1)}{2}, ~ 1 \le 边权 \le 10^9$

题解

这玩意儿好像和求什么图的绝对中心是一样的，图的绝对中心就是指一个中心，到最远的点路径最短

那就通过图的绝对中心来求解这道题

假设改图的绝对中心为点 $p$，那么它可以是某条边的端点也可以在某条边上

首先有一个结论

距离 $p$ 最远的点至少有两个点 $u, v$，并且它们到 $p$ 的距离相等

这条结论很容易证明，若 $dis (u, p) \ne dis (v, p)$，那么将点 $p$ 往较远的那个端点稍微移动一下即可得到更优的答案此时假定 $p$ 在边 $(u, v)$ 上，$(u, v)$ 长 $L$，$p$ 距离点 $u$ 为 $x$，那么任意一点 $s$ 到 $p$ 的距离即为 $\min(dis (s, u) + x, dis (s, v) + L - x)$

可以发现，这个距离以函数形式表示出来是一条折线（上升部分斜率为 $1$，下降部分 $- 1$）

（图源来自论文《Play with Trees Solutions》）

然后你就可以搞出 $n$ 条折线，其中横坐标对应每一种 $x$ 的取值，所以同一 $x$ 坐标对应同一个中心

而要求的是所有距离中的最大值，这对应实线部分

你又要保证最大的最小，故只需在实现部分取最小即为答案，通过图像可以看出，该最小值点一定为某两条折线的交点

那么就可以枚举所有点对 $(u, v)$，并按 $dis_{u, s}$ 进行排序，用扫描的做法求解了

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstdio>
#include <cstring>

using namespace std;

typedef long long LL;

const int MAXN = 500 + 10;

const LL INF = 0x3f3f3f3f3f3f3f3f;

int N, M;
LL f[MAXN][MAXN]= {0};
int rnk[MAXN][MAXN]= {0};

inline int getnum () {
	int num = 0; char ch = getchar ();
	while (! isdigit (ch)) ch = getchar ();
	while (isdigit (ch)) num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();
	return num;
}

int main () {
	N = getnum (), M = getnum ();
	for (int i = 1; i <= N; i ++)
		for (int j = i + 1; j <= N; j ++)
			f[i][j] = f[j][i] = INF;
	for (int i = 1; i <= M; i ++) {
		int u = getnum (), v = getnum (), w = getnum ();
		f[u][v] = f[v][u] = w;
	}
	for (int k = 1; k <= N; k ++)
		for (int i = 1; i <= N; i ++)
			for (int j = 1; j <= N; j ++)
				f[i][j] = min (f[i][j], f[i][k] + f[k][j]);
	for (int i = 1; i <= N; i ++) {
		for (int j = 1; j <= N; j ++) rnk[i][j] = j;
		for (int j = 1; j <= N; j ++)
			for (int k = j + 1; k <= N; k ++)
				if (f[i][rnk[i][j]] > f[i][rnk[i][k]])
					swap (rnk[i][j], rnk[i][k]);
	}
	LL ans = INF;
	for (int u = 1; u <= N; u ++)
		for (int v = 1; v <= N; v ++) {
			ans = min (ans, f[u][rnk[u][N]] << 1); // 中心取端点处
			ans = min (ans, f[v][rnk[v][N]] << 1);
			int k = N;
			for (int i = N - 1; i >= 1; i --)
				if (f[v][rnk[u][i]] > f[v][rnk[u][k]]) { // 判断两折线是否有交
					ans = min (ans, f[u][rnk[u][i]] + f[u][v] + f[v][rnk[u][k]]);
					k = i;
				}
		}
	cout << ans << endl;

	return 0;
}

Problem C