2024 NFLS 集训记录

题解/做题记录
148k 词

Legacy

TopCoder XorBoard

给定 H,W,R,C,SH, W, R, C, S，给一个 H×WH \times W 的网格，初始全为白色，每次可以选一列或选一行白变黑、黑变白，问行操作 RR 次，列操作 LL 次，最终黑色面积为 SS 的方案数。两种操作不同当且仅当存在一行或一列被操作的次数不同。

枚举染了几行几列然后算方案数即可。

TopCoder ConversionMachine

给定两个字符集为 {a,b,c}\{\texttt{a},\texttt{b},\texttt{c}\} 的字符串 s,ts, t，每次操作可以对 ss 的某个位置的字符向后变一位，给出每个字符变成下一个字符的代价和最大代价问把 ss 变成 tt 的方案数。

每个位置都是先还原后再进行若干组 a→b→c→a\texttt{a} \to \texttt{b} \to \texttt{c} \to \texttt{a} 的轮换，所以可以确定总的操作次数上限，然后设 dpi,jdp _ {i, j} 表示还有 ii 个位置需要操作 11 次，jj 个位置需要操作 22 次的方案数，矩阵快速幂优化即可。

TopCoder CosmicBlocks

懒得写题面了。

发现颜色数很少，所以可以暴力枚举所有 DAG 然后判合法，合法当且仅当可以分层（即任意两点之间有边当且仅当后一个点在前一个点的后一层）且任意两层之间满足要求。

考虑两层之间的限制，相当于要上下两层的积木进行匹配，满足有边的颜色之间至少有一组匹配且存在完美匹配，用霍尔定理 check 即可。

TopCoder KingdomAndCities

给定 n,m,kn, m, k，求 nn 个点 kk 条边的简单无向连通图的数量，使得对于编号 ≤m\le m 的 mm 个点，都恰好有两条连边。m≤2m \le 2。

考虑 m=0m = 0 时怎么做，枚举第一个点所在连通块大小进行容斥。

然后考虑把前 mm 个点先都看成原图的边，然后再裂成点，这样分讨若干种情况即可。

TopCoder SweetFruits

懒得写题面了。

考虑甜的水果除了甜度没有区别，于是设 fif _ i 表示有 ii 个真正甜的水果的方案数，然后枚举哪些是真正甜的即可。求 fif _ i 可以矩阵树加二项式定理，然后数据范围i比较大需要 meet-in-middle 优化枚举。

3.15

TopCoder FoxAndFlowerShopDivOne

给定一个 n×mn \times m 的网格，每个格子是 L 或 P 或 .，求两个不交子矩形使得 L 的数量之和减去 P 的数量之和的绝对值不超过 kk，且 L 和 P 的数量总和最大。

枚举两个子矩形的分割线，一定是一条横线或一条竖线，然后双指针即可。

TopCoder Barracks

懒得写题面了。

大分讨。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int mine, hp, per, ans = -1;

int main() {
	scanf("%d%d%d", &mine, &hp, &per);
	if (hp <= mine) {puts("1"); return 0;}
	if (per >= mine * 2) {puts("-1"); return 0;}
	if (per < mine) {
		hp -= mine;
		int round = 1;
		while (hp > mine) hp -= mine - per, round++;
		for (int i = 0; i <= hp; i++) {
			if (i * (mine - per) >= hp) {
				if (ans == -1 || (round + i) < ans) ans = round + i;
				continue;
			}
			int h = hp - i * (mine - per), n = per - (mine - h), my = mine - n;
			int now = round + i + 1;
			while (1) {
				now++;
				n -= my;
				if (n <= 0) break;
				my -= n;
				if (my <= 0) {now = -1; break;}
			}
			if (now != -1 && (ans == -1 || now < ans)) ans = now;
		}
		printf("%d\n", ans);
		return 0;
	}
	hp -= mine;
	if (hp > mine) {puts("-1"); return 0;}
	int n = per - mine + hp, round = 2;
	if (n >= mine) {puts("-1"); return 0;}
	mine -= n;
	while (1) {
		round++;
		n -= mine;
		if (n <= 0) break;
		mine -= n;
		if (mine <= 0) {puts("-1"); return 0;}
	}
	ans = round;
	printf("%d\n", ans);
	return 0;
}

TopCoder MegaFactorial

定义：

f(n,k)={f(n,k−1)f(n−1,k)n>0,k>01n=0nk=0f(n, k) = \begin{cases} f(n, k - 1) f(n - 1, k) & n > 0, k > 0 \\ 1 & n = 0 \\ n & k = 0 \end{cases}

给定 n,k,bn, k, b，求 f(n,k)f(n, k) 中 bb 因子的个数。

首先 bb 的因子里只有最大的质因数的幂次会成为答案，因此可以把 BB 转化成最大的质因数的幂次，然后求出这个质因数的个数再除掉指数下取整即可得到答案。

然后考虑质数咋做，那就是枚举其幂次，然后对于每个枚举的 xx，在 (kx,0)(kx, 0) 处会多 11，那么连续的 xx 行一组，矩阵快速幂优化 DP 即可。

TopCoder BoundedOptimization

有若干个变量和一个式子，该式子是若干项某两个变量相乘相加，保证不会出现同一个变量相乘且每项两两不同，对于每个变量限制其值为某个区间，并限制所有变量的和的上界，求式子的最大值。

随机。

每个随机两个变量，限制其他变量不变且这个变量的和不变，可以 O(1)O(1) 求出让式子最大的两个变量的取值，然后再每隔一段时间随机扰动一下。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <chrono>
#include <random>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

int n, a[15][15], l[15], r[15], p[15], limit;
double v[15];
string expr;

double calc() {
	double res = 0;
	for (int i = 1; i <= n; i++)
		for (int j = 1; j < i; j++) res += a[i][j] * v[i] * v[j];
	return res;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		expr += s;
	}
	for (int i = 0; i < (int)expr.length(); i += 3)
		a[expr[i] - 'a' + 1][expr[i + 1] - 'a' + 1] = a[expr[i + 1] - 'a' + 1][expr[i] - 'a' + 1] = 1;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &l[i]);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &r[i]);
	scanf("%d", &limit);
	for (int i = 1; i <= n; i++) limit -= l[i], p[i] = i;
	shuffle(p + 1, p + n + 1, gen);
	for (int i = 1; i <= n; i++) {
		v[p[i]] = min(limit, r[p[i]] - l[p[i]]);
		limit -= v[p[i]];
		v[p[i]] += l[p[i]];
	}
	double ans = calc();
	for (int T = 1; T <= 5000000; T++) {
		int x, y;
		do x = gen() % n + 1, y = gen() % n + 1;
		while (x == y);
		double sum = v[x] + v[y];
		double le = max((double)l[x], sum - r[y]), ri = min((double)r[x], sum - l[y]);
		if (T % 100000 == 0) {
			v[x] = le + (ri - le) * (gen() % 1000001 / 1000000.0);
			v[y] = sum - v[x];
			ans = max(ans, calc());
			continue;
		}
		double p = 0, q = 0;
		for (int i = 1; i <= n; i++) {
			if (a[x][i] && i != y) p += v[i];
			if (a[y][i] && i != x) q += v[i];
		}
		if (a[x][y]) {
			v[x] = min(max((p - q + sum) / 2, le), ri);
			v[y] = sum - v[x];
		} else {
			v[x] = (p < q ? le : ri);
			v[y] = sum - v[x];
		}
		ans = max(ans, calc());
	}
	// for (int i = 1; i <= n; i++) eprintf("%lf ", v[i]);
	// eputs("");
	// eprintf("%lf\n", ans);
	printf("%.12lf\n", ans);
	return 0;
}

3.16

TopCoder LeftRightDigitsGame2

有 nn 张卡牌，每张卡牌上有一个数码，每次取出最前面一张卡牌放到桌子上已有卡牌的左侧或右侧，要求组成的数大于等于某个给定的数，求得到的数最小。

设 dpi,j,0/1dp _ {i, j, 0 / 1} 表示前 ii 张牌对应给定数的 jj 到 j+i−1j + i - 1 张牌，凑成的数等于或大于时最小是多少，暴力转移即可做到 O(n3)O(n ^ 3)。

TopCoder YetAnotherHamiltonianPath

给定 nn 个字符串 sis _ i，点 ii 和 点 jj 之间的边权值为 ∣si∣2+∣sj∣2−∣LCP(si,sj)∣2|s _ i| ^ 2 + |s _ j| ^ 2 - |LCP(s _ i, s _ j)| ^ 2，求从 00 出发到 11 的最短哈密顿路径。

建出 Trie，不限制起点终点时就是顺序遍历，限制时则最后跑 0,10, 1 的 LCA 的 11 所在的子树。调整证明即可。

TopCoder NumberMagic

给定 n,mn, m，要构造 kk 张卡牌，每张上有恰好 mm 个数字，使得对于任意一个数，都能确定一个卡牌的子集，使得子集中卡牌上数字的交减去子集外卡牌上数字的并为该数字。求最小的 kk。

首先答案可以二分。

相当于要构造 n×kn \times k 的 01 矩阵，每列恰好 mm 个 11，使得每行互不相同。

然后考虑有 mkmk 个 11，要构造 nn 个不同的长度为 kk 的二进制串，需要的最少和最多的 11 的个数，显然 mkmk 要在这个区间内。

然后这个条件也是充分的，证明可以参考 CF201E。

TopCoder Orienteering

给定一个网格，有些位子是障碍，空地构成一棵树，有 mm 个特殊点，等概率选取 kk 个特殊点，问从任意位置开始走走完 kk 个特殊点的最短路径的期望长度。

相当于虚树边数 ×2\times 2 减去虚树直径，虚树边数直接求，直径就枚举两个特殊点令他们为直径，则其他特殊点到这两个点的距离不能超过这两个点之间的距离，暴力枚举即可。

3.18

TopCoder DefectiveAddition

给定序列 A1,A2,…,AnA _ 1, A _ 2, \ldots, A _ n 和 mm，构造 B1,B2,…BnB _ 1, B _ 2, \ldots B _ n 使得 Bi≤AiB _ i \le A _ i 且异或和为 mm，求方案数。

枚举第一个有数不取到上界的位，则下面的位除了这个数以外可以随便填。设 dpi,0/1dp _ {i, 0 / 1} 表示这一位前 ii 个数，这一位异或和为 0/10 / 1 时下面的位 +1+ 1 的乘积，枚举第一个没取到上界的数统计答案即可。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 1e9 + 7;

int n, a[55], m, dp[55][2], ans, Xor = 0;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), Xor ^= a[i];
	scanf("%d", &m);
	if (Xor == m) ans++;
	for (int i = 30; i >= 0; i--) {
		int Xor = 0;
		for (int j = 1; j <= n; j++) Xor ^= a[j] >> (i + 1) << (i + 1);
		if (Xor != (m >> (i + 1) << (i + 1))) break;
		vector<int> vec;
		vec.push_back(0);
		int sum = 1;
		for (int j = 1; j <= n; j++)
			if (a[j] >> i & 1) vec.push_back(a[j] & ((1 << i) - 1));
			else sum = (long long)sum * ((a[j] & ((1 << i) - 1)) + 1) % mod;
		dp[0][0] = 1;
		for (int j = 1; j < (int)vec.size(); j++) {
			dp[j][0] = ((long long)dp[j - 1][0] * (1 << i) + (long long)dp[j - 1][1] * (vec[j] + 1)) % mod;
			dp[j][1] = ((long long)dp[j - 1][0] * (vec[j] + 1) + (long long)dp[j - 1][1] * (1 << i)) % mod;
		}
		int lst = 1, res = 0;
		for (int j = (int)vec.size() - 1; j >= 1; j--) {
			int id = ((vec.size() - j - 1) & 1) ^ (m >> i & 1);
			// if (i == 1) eprintf("de: %d %d %d\n", j, n >> i & 1, dp[j - 1][id]);
			res = (res + (long long)sum * dp[j - 1][id] % mod * lst) % mod;
			lst = (long long)lst * (vec[j] + 1) % mod;
		}
		// eprintf("%d %d\n", i, res);
		ans = (ans + res) % mod;
	}
	printf("%d\n", ans);
	return 0;
}

TopCoder CoinsGame

有一个 n×mn \times m 的网格，有些位置是障碍，要在若干个空位上放硬币，使得存在一种操作方式使至少一个硬币移到网格外且至少一个硬币留在网格内。操作是每次选择上下左右的一个方向，所有硬币向该方向移动一格，若有障碍则不动。求放硬币的方案数。

考虑找出所有合法的硬币对，可以从最终位置开始 bfs。然后发现不合法具有传递性，即放 a,ba, b 无法满足要求，放 b,cb, c 无法满足要求，则放 a,ca, c 也无法满足要求，因此找出所有不合法等价类即可计算答案。

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
105
106
107
108
109
110
111
112
113
114
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 1e9 + 9, gx[] = {1, 0, 0, -1}, gy[] = {0, 1, -1, 0};

int n, m, num, vis[1605][1605], cnt[1605], f[1605];
char ch[45][45];
queue<pair<int, int>> q;
struct dsu {
	int fa[1605];
	
	dsu() {for (int i = 1; i < 1605; i++) fa[i] = i;}
	int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
	void merge(int x, int y) {fa[find(x)] = find(y); return ;}
} d;

int getid(int x, int y) {return (x - 1) * m + y;}
int power(int a, int b) {
	int ans = 1;
	while (b) {
		if (b & 1) ans = (long long)ans * a % mod;
		a = (long long)a * a % mod;
		b >>= 1;
	}
	return ans % mod;
}
int checkout(int i, int k) {
	int x = (i + m - 1) / m, y = i % m;
	if (!y) y = m;
	if (ch[x][y]== '#') return 0;
	int xx = x + gx[k], yy = y + gy[k];
	return xx < 1 || xx > n || yy < 1 || yy > m;
}
int checkok(int i, int k) {
	int x = (i + m - 1) / m, y = i % m;
	if (!y) y = m;
	if (ch[x][y]== '#') return 0;
	int xx = x + gx[k], yy = y + gy[k];
	return 1 <= xx && xx <= n && 1 <= yy && yy <= m;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		m = s.length();
		s = " " + s;
		for (int j = 1; j <= m; j++)
			ch[i][j] = s[j], num += ch[i][j] == '.', f[getid(i, j)] = ch[i][j] == '.';
	}
	// eprintf("%d\n", checkok(3, 2));
	for (int i = 1; i <= n * m; i++)
		for (int j = 1; j <= n * m; j++)
			for (int k = 0; k < 4; k++)
				if (checkout(i, k) && checkok(j, k)) {
					q.emplace(i, j), vis[i][j] = 1;
					break;
				}
	while (!q.empty()) {
		int u = q.front().first, v = q.front().second;
		q.pop();
		int ux = (u + m - 1) / m, uy = u % m, vx = (v + m - 1) / m, vy = v % m;
		if (!uy) uy = m;
		if (!vy) vy = m;
		// eprintf("%d %d\n", u, v);
		// eprintf("%d %d %d %d\n", ux, uy, vx, vy);
		for (int i = 0; i < 4; i++) {
			int uxx = ux + gx[i], uyy = uy + gy[i], vxx = vx + gx[i], vyy = vy + gy[i];
			if (ch[uxx][uyy] != '.' || ch[vxx][vyy] != '.') continue;
			if (vis[getid(uxx, uyy)][getid(vxx, vyy)]) continue;
			q.emplace(getid(uxx, uyy), getid(vxx, vyy));
			vis[getid(uxx, uyy)][getid(vxx, vyy)] = 1;
		}
		for (int i = 0; i < 4; i++) {
			int uxx = ux + gx[i], uyy = uy + gy[i], vxx = vx + gx[3 - i], vyy = vy + gy[3 - i];
			if (ch[uxx][uyy] != '.' || ch[vxx][vyy] != '#') continue;
			if (vis[getid(uxx, uyy)][getid(vx, vy)]) continue;
			q.emplace(getid(uxx, uyy), getid(vx, vy));
			vis[getid(uxx, uyy)][getid(vx, vy)] = 1;
		}
		for (int i = 0; i < 4; i++) {
			int uxx = ux + gx[i], uyy = uy + gy[i], vxx = vx + gx[3 - i], vyy = vy + gy[3 - i];
			if (ch[uxx][uyy] != '#' || ch[vxx][vyy] != '.') continue;
			if (vis[getid(ux, uy)][getid(vxx, vyy)]) continue;
			q.emplace(getid(ux, uy), getid(vxx, vyy));
			vis[getid(ux, uy)][getid(vxx, vyy)] = 1;
		}
	}
	for (int i = 1; i <= n * m; i++) if (f[i])
		for (int j = i + 1; j <= n * m; j++) if (f[j])
			if (!vis[i][j] && !vis[j][i]) d.merge(i, j);
	for (int i = 1; i <= n * m; i++)
		if (f[i]) cnt[d.find(i)]++;
	int ans = (power(2, num) + mod - 1) % mod;
	// eprintf("%d\n", ans);
	// for (int i = 1; i <= n * m; i++)
	// 	for (int j = i; j <= i; j++)
	// 		if (vis[i][i]) eputs("?");
	for (int i = 1; i <= n * m; i++)
		if (cnt[i]) ans = (ans + mod - power(2, cnt[i]) + 1) % mod;
	printf("%d\n", ans);
	return 0;
}

另一种方法是，发现等价于将每个空位看作状态，有上下左右四种转移，求最小 DFA，直接 Hopcroft 即可。

TopCoder Mountains

题面懒得写了。

考虑从后往前放山，每座山出现在一个区间，设 mxhimxh _ i 为第 ii 列已有山的高度，列不等式发现当目标区间左端点或右端点不是边界（即 11 和 WW）时合法位置至多两个，而都顶到边界或这座山无法看到时总方案数为 WW，则所有方案数为 O(W2n)O(W 2 ^ n)，可以直接爆搜。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 1e9 + 9;

int n, W, h[15], l[15], r[15];
map<string, int> mp[15];

string encode(int *mxh) {
	string s = "";
	for (int i = 1; i <= W; i++) s += to_string(mxh[i]) + "#";
	return s;
}
void decode(string s, int *mxh) {
	int val = 0, idx = 0;
	for (char i : s)
		if (isdigit(i)) val = val * 10 + i - '0';
		else mxh[++idx] = val, val = 0;
	return ;
}
int check(int *mxh, int pos, int h, int l, int r) {
	int le = 1e9, ri = 0;
	for (int j = 1; j <= W; j++)
		if (h - abs(pos - j) > mxh[j]) le = min(le, j), ri = max(ri, j);
	if (!l && le > ri) return 1;
	return le == l && ri == r;
}
int dfs(string s, int now) {
	if (now == 0) return 1;
	if (mp[now].count(s)) return mp[now][s];
	int mxh[55];
	decode(s, mxh);
	// if (now == 2) {
	// 	for (int i = 1; i <= W; i++) eprintf("%d ", mxh[i]);
	// 	eputs("");
	// }
	// if (!l[now]) return mp[now][s] = (long long)W * dfs(s, now - 1) % mod;
	int res = 0;
	for (int i = 1; i <= W; i++)
		if (check(mxh, i, h[now], l[now], r[now])) {
			// if (now == 3) eputs("?");
			int nxth[55];
			for (int j = 1; j <= W; j++) nxth[j] = max(mxh[j], h[now] - abs(i - j));
			res = (res + dfs(encode(nxth), now - 1)) % mod;
		}
	return mp[now][s] = res;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &h[i]);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		W = s.length();
		s = " " + s;
		for(int j = 1; j <= W; j++)
			if (s[j] == 'X') {
				if (!l[i]) l[i] = j;
				r[i] = j;
			}
	}
	string s = "";
	for (int i = 1; i <= W; i++) s += "0#";
	printf("%d\n", dfs(s, n));
	return 0;
}

TopCoder Tunnels

题面懒得写了。

答辩题，从上往下考虑，将上面的已有路径与下面匹配，设 dpi,a,bdp _ {i, a, b} 表示前 ii 行，左边有 aa 条能与下面匹配，右边有 bb 条时最大的匹配数，分讨转移即可。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int gx[] = {1, -1, 0, 0}, gy[] = {0, 0, -1, 1};
int n, m, cnt, id[55][55];
char ch[55][55];
int deg[55][55], mn[2505], mx[2505];
int lu[55], ld[55], ru[55], rd[55], lr[55];
int dp[55][55][55], ans;

int dfs(int x, int y, int c) {
	if (x < 1 || x > n || y < 1 || y > m || ch[x][y] == '.') return 0;
	if (id[x][y]) return 1;
	id[x][y] = c;
	mn[c] = min(mn[c], x);
	mx[c] = max(mx[c], x);
	for (int d = 0; d < 4; d++) deg[x][y] += dfs(x + gx[d], y + gy[d], c);
	return 1;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		m = s.length();
		s = " " + s;
		for (int j = 1; j <= m; j++) ch[i][j] = s[j];
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			if (ch[i][j] == 'X' && !id[i][j]) mn[++cnt] = n + 1, dfs(i, j, cnt);
	if (cnt == 0) {puts("0"); return 0;}
	if (m == 1) {puts("1"); return 0;}
	for (int i = 1; i <= n; i++) {
		if (ch[i][1] == 'X' && deg[i][1] <= 1) {
			if (i != 1 && i == mn[id[i][1]]) lu[i] = 1;
			else if (i == mx[id[i][1]]) ld[i] = 1;
		}
		if (ch[i][m] == 'X' && deg[i][m] <= 1) {
			if (i != 1 && i == mn[id[i][m]]) ru[i] = 1;
			else if (i == mx[id[i][m]]) rd[i] = 1;
		}
		lr[i] = mn[id[i][1]] == i && mx[id[i][1]] == i;
		for (int j = 1; j <= m; j++) lr[i] &= ch[i][j] == 'X';
		if (lr[i]) lu[i] = ru[i] = ld[i] = rd[i] = 1;
	}
	for (int i = 1; i < n; i++) {
		if (lu[i] && ld[i + 1]) ld[i + 1] = 0;
		if (ru[i] && rd[i + 1]) rd[i + 1] = 0;
	}
	memset(dp, ~0x3f, sizeof(dp));
	ans = dp[0][0][0];
	dp[0][0][0] = 0;
	for (int i = 1; i <= n; i++)
		for (int a = 0; a <= i; a++)
			for (int b = 0; b <= i; b++) {
				for (int l = -1; l <= 1; l++)
					for (int r = -1; r <= 1; r++) {
						if (a - l < 0 || b - r < 0) continue;
						if (lr[i] && l == r && !(l == 0 && i == 1)) continue;
						if (l == -1 && !lu[i]) continue;
						if (l == 1 && !ld[i]) continue;
						if (r == -1 && !ru[i]) continue;
						if (r == 1 && !rd[i]) continue;
						dp[i][a][b] = max(dp[i][a][b], dp[i - 1][a - l][b - r] + (l == -1) + (r == -1));
					}
			}
	for (int a = 0; a <= n; a++)
		for (int b = 0; b <= n; b++) ans = max(ans, dp[n][a][b]);
	printf("%d\n", cnt - ans);
	return 0;
}

3.19

TopCoder XorAndSum

给定一个序列，每次可以选择两个数，将第一个数变成两数的异或，操作次数不限，求最终序列中所有数和的最大值。

首先搞出线性基，对于不在线性基中的数直接取到线性基中数的异或和。然后考虑线性基中的数。

发现一定可以转化成一个数一个数操作，然后考虑第一个数一定是变成异或和最优，对于剩下的数，显然先异或上异或和，然后再用其他数去凑最大值。因为无论如何变化线性基张成的空间不变所以可以这样搞。然后发现第一个数取最大的那个最优，就做完了。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n;
struct LinearBasis {
	long long b[55];

	void insert(long long x) {
		for (int i = 51; i >= 0; i--)
			if (x >> i & 1) {
				if (!b[i]) {b[i] = x; break;}
				else x ^= b[i];
			}
		return ;
	}
	long long query(long long x) {
		for (int i = 51; i >= 0; i--)
			if ((x ^ b[i]) > x) x ^= b[i];
		return x;
	}
	long long getmin(long long x) {
		for (int i = 51; i >= 0; i--)
			if ((x ^ b[i]) < x) x ^= b[i];
		return x;
	}
} lb;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		long long x;
		scanf("%lld", &x);
		lb.insert(x);
	}
	long long val = lb.query(0);
	int num = n;
	for (int i = 51; i >= 0; i--)
		if (lb.b[i]) num--;
	// for (int i = 0; i <= 51; i++) eprintf("%lld ", lb.b[i]);
	// eputs("");
	long long ans = val * num;
	for (int i = 51, flag = 0; i >= 0; i--)
		if (lb.b[i]) {
			if (!flag) ans += val;
			else {
				long long tmp = lb.b[i];
				lb.b[i] = 0;
				ans += val ^ lb.getmin(tmp);
				// eprintf("%d %lld\n", i, lb.getmin(tmp));
				lb.b[i] = tmp;
			}
			flag = 1;
		}
	printf("%lld\n", ans);
	return 0;
}

TopCoder AlienDictionary

给定若干个由 ?，A，B 组成的串，多次询问 kk，求由 A, B 组成的，长度位为 nn 的，合法的，字典序第 kk 小的串，其中合法是不存在一个子串与先前给定的串匹配，其中 ? 可以匹配 A 或 B。

暴力拆开 ? 建 AC 自动机，设 dpi,jdp _ {i, j} 表示从 jj 走 ii 步走到最终状态的方案数，然后试填法求答案。

TopCoder NextAndPrev

给定两个串，每次可以将第一个串的某种字符变成下一个或上一个字符，变成上一个或下一个分别需要一定代价，求将第一个串变成第二个串的最小代价。

首先 check 是否有解，一个必要条件是每种字符对应一个区间。然后考虑环上做起来很麻烦，那么将目标偏移若干个 2626，然后变成数轴上的问题，数轴上就直接来了。

check 就考虑枚举断点把他断开看能否划分区间即可。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <tuple>
#include <chrono>
#include <random>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

int nxtc, prec, n;
string s, t;
unsigned long long ps[52], pt[26];

int check() {
	for (int i = 0; i < 26; i++)
		if (!pt[i]) return 0;
	return 1;
}
int getpos(unsigned long long sum) {
	for (int i = 0; i < 26; i++)
		if (pt[i] == sum) return i;
	return -1;
}
int calc(unsigned long long *ps, int shift) {
	vector<tuple<int, int, int>> vec;
	for (int l = 0, r; l < 26; l = r + 1) {
		r = l;
		if (!ps[l]) continue;
		unsigned long long sum = ps[l];
		while (r < 26 && getpos(sum) == -1) sum += ps[++r];
		if (r == 26) return 0x3f3f3f3f;
		vec.emplace_back(l, r, getpos(sum) - shift);
		// eprintf("%d %d %d\n", l, r, getpos(sum) - shift);
	}
	// eprintf("%d\n", shift);
	int len = 0;
	for (int i = 0; i < (int)vec.size(); i++) {
		int x = get<2>(vec[i]), y = get<2>(vec[(i + 1) % vec.size()]);
		len += y - x + (y < x ? 26 : 0);
	}
	if (vec.size() > 1 && len != 26) return 0x3f3f3f3f;
	int ans = 0x3f3f3f3f;
	for (auto &i : vec)
		if (get<2>(i) > get<2>(vec.back())) get<2>(i) -= 26;
	for (int i = -4; i <= 4; i++) {
		int res = 0;
		for (auto j : vec) {
			int l = get<0>(j), r = get<1>(j), p = get<2>(j) + i * 26;
			if (p <= l) res += prec * (r - p);
			else if (p >= r) res += nxtc * (p - l);
			else res += nxtc * (p - l) + prec * (r - p);
		}
		ans = min(ans, res);
	}
	return ans;
}

int main() {
	scanf("%d%d", &nxtc, &prec);
	cin >> s >> t;
	n = s.length();
	for (int i = 0; i < n; i++) {
		unsigned rnd = gen();
		ps[s[i] - 'a'] += rnd, pt[t[i] - 'a'] += rnd;
	}
	if (s == t) {puts("0"); return 0;}
	if (check()) {puts("-1"); return 0;}
	for (int i = 0; i < 26; i++) ps[26 + i] = ps[i];
	int ans = 0x3f3f3f3f;
	for (int i = 0; i < 26; i++) ans = min(ans, calc(ps + i, i));
	if (ans != 0x3f3f3f3f) printf("%d\n", ans);
	else puts("-1");
	return 0;
}

TopCoder MaximalTriangle

给一个正 nn 边形，求有多少种三角剖分的方式，使得存在一个三角形面积严格大于其他三角形。

枚举最大的三角形，把多边形切成三个部分，要求每部分最大面积小于枚举的三角形的面积。设 gi,jg _ {i, j} 表示 ii 个点，面积小于等于 jj 的方案数，枚举不在多边形上的那条边（即切割的弦）所在的三角形转移即可。

最恶心的是直接预处理过不去，所以每次枚举都重新 DP，然后面积上界只枚举到枚举的面积再卡卡常。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

struct FastMod {
  typedef unsigned long long ULL;
  typedef __uint128_t LLL;
  ULL b, m;
  void init(ULL b) { this->b = b, m = ULL((LLL(1) << 64) / b); }
  ULL operator()(ULL a){
    ULL q = (ULL)((LLL(m) * a) >> 64);
    ULL r = a - q * b;
    return r >= b ? r - b : r;
  }
} M;
inline long long mul(int a, int b) { return M(1ull * a * b); }

const double pi = acos(-1), eps = 1e-5;

struct Vect {
	double x, y;

	Vect(double _x = 0, double _y = 0): x(_x), y(_y) {}
	double operator*(const Vect &u) const {return x * u.y - y * u.x;}
};

int n, mod, m;
long long g[505];
double S[505][505];

double calcS(int i, int j) {
	int x = n - i - j;
	if (x < i) swap(i, x);
	if (x < j) swap(j, x);
	if (j < i) swap(i, j);
	j += i;
	return Vect(cos(2 * pi / n * i) - 1, sin(2 * pi / n * i)) *
		Vect(cos(2 * pi / n * j) - 1, sin(2 * pi / n * j)) *
		1e5;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> mod;
	M.init(mod);
	for (int i = 1; i < n; i++)
		for (int j = i + 1; j < n; j++) S[i][j - i] = calcS(i, j - i);
	long long ans = 0;
	for (int i = 1; i < n; i++)
		for (int j = i + 1; j < n; j++) {
			int x = i, y = j - i, z = n - x - y;
			if (x > y || y > z) continue;
			memset(g, 0, sizeof(g));
			g[2] = 1;
			for (int i = 2; i <= z + 1; i++) {
				g[i] %= mod;
				for (int j = 2, to = i + 1; j <= i && to <= z + 1; j++, to++) {
					const int o = (j < i);
					if (S[i - 1][j - 1] < S[x][y] - eps) g[to] += mul(g[i], g[j]) << o;
				}
			}
			int c = 2 * n;
			if (x == y || y == z) c = n;
			if (x == y && y == z) c = n / 3;
			ans = (ans + g[x + 1] * g[y + 1] % mod * g[z + 1] % mod * c) % mod;
		}
	cout << ans % mod << '\n';
	return 0;
}
/*
444
998244353
860426962
*/

TopCoder DisjointSemicircles

数轴上排列着等距离的 2n2n 个点，要用若干个半圆两两匹配。使得任意两个半圆不交。已经有了若干组匹配但没有确定方向，求是否有解。

先确定每个点的半圆在上面还是下面，然后结论是：存在一组解当且仅当对于任意已有的半圆，其内部与之同向的点的个数为偶数。

证明可以调整。

然后考虑设 xix _ i 为 ii 的方向，则要求：

  • ⨁i=12nxi=0\bigoplus _ {i = 1} ^ {2n} x _ i = 0。
  • 对于任意已有匹配 l,rl, r，xl⊕xr=0x _ l \oplus x _ r = 0。
  • 对于已有匹配 l,r,l′,r′l, r, l', r'，若相交，则 xl⊕xl′=1x _ l \oplus x _ {l'} = 1。
  • 对于任意已有匹配 l,rl, r，⨁i=l+1r−1(xi⊕xl⊕1)=0\bigoplus _ {i = l + 1} ^ {r - 1} (x _ i \oplus x _ l \oplus 1) = 0。

发现中间两个都是两个点之间的限制，用带权并查集维护，剩下两个列方程，然后高斯消元判断是否无解即可。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <bitset>
#include <cstdio>
#include <string>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, a[55], l[55], r[55];
struct LinearBasis {
	bitset<55> b[55];

	void insert(bitset<55> x) {
		for (int i = n; i >= 0; i--)
			if (x[i]) {
				if (!b[i].count()) {b[i] = x; return ;}
				else x ^= b[i];
			}
		return ;
	}
} lb;
struct dsu {
	int fa[55], val[55];

	dsu() {for (int i = 1; i < 55; i++) fa[i] = i, val[i] = 0;}
	int find(int x) {
		if (x == fa[x]) return x;
		else {
			int rt = find(fa[x]);
			val[x] ^= val[fa[x]];
			fa[x] = rt;
			return rt;
		}
	}
	int getval(int x) {find(x); return val[x];}
	void merge(int x, int y, int v) {
		int fx = find(x), fy = find(y);
		if (fx == fy) {
			if ((getval(x) ^ getval(y)) != v) {puts("IMPOSSIBLE"); exit(0);}
			return ;
		}
		val[fx] = getval(x) ^ v ^ getval(y);
		fa[fx] = fy;
		return ;
	}
} d;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		if (a[i] == -1) continue;
		if (!l[a[i]]) l[a[i]] = i;
		else r[a[i]] = i;
	}
	for (int i = 0; i < n / 2; i++) if (l[i]) {
		d.merge(l[i], r[i], 0);
		for (int j = 0; j < n / 2; j++)
			if (i != j && l[j] && l[i] < l[j] && l[j] < r[i] && r[i] < r[j]) d.merge(l[i], l[j], 1);
	}
	bitset<55> b;
	for (int i = 1; i <= n; i++) {
		b[d.find(i)].flip();
		if (d.getval(i)) b[0].flip();
	}
	lb.insert(b);
	for (int i = 0; i < n / 2; i++)
		if (l[i]) {
			b.reset();
			for (int j = l[i] + 1; j < r[i]; j++) {
				b[d.find(l[i])].flip();
				if (d.getval(l[i])) b[0].flip();
				b[0].flip();
				b[d.find(j)].flip();
				if (d.getval(j)) b[0].flip();
			}
			lb.insert(b);
		}
	if (lb.b[0].count()) puts("IMPOSSIBLE");
	else puts("POSSIBLE");
	return 0;
}

3.22

A

给一个字符串 ss，求合法的字符串 tt 的数量，使得 ∣t∣=∣s∣|t| = |s|，且 tt 中一个子串是回文串当且仅当 ss 中这个位置的子串是回文串。

考虑怎么样的串是满足条件的，发现建出 PAM，如果两个串的 PAM 同构且每个点所在的位置相同则符合条件。于是有一个直接的想法就是对 ss 建 PAM，然后对于值要相同的位置连一条边权为 00 的边，要不同的位置连一条边权为 11 的边，则只要 00 边连接的两个点相同，11 边连接的两个点不同即可。

考虑用并查集缩 00 边，然后变成给一张图每个点染色使得相邻点颜色不同。这个显然不可做，于是考虑着一些性质。

如果一个点连接的点两两有边就好做了，然后容易证明确实是这样，然后就做完了。

然而 PAM 会被卡常，考虑这个连边的本质，相当于对于每个极长回文子串，对称的位置要相同，两边的位置要不同，考虑用 Manacher 维护，容易证明只需要在扩展时连边即可。

B

给一张 nn 个点的完全图，每条边权值为 ii 的概率为 pip _ i，特别地，权值为 00 表示这条边不存在，求图连通且最小生成树打小为 n−1∼k(n−1)n - 1 \sim k (n - 1) 的概率（kk 是边权可能的最大值）。

设 fv,i,jf _ {v, i, j} 表示只考虑边权 ≤v\le v 时，有 ii 个点且最小生成树为 jj 的概率，常见做法是枚举 11 所在连通块大小容斥。

转移需要用到 gv,i,jg _ {v, i, j} 表示只考虑边权 <v< v，令不存在的边变成边权为 vv 时的概率。

fv,i,j=gv,i,j−∑x=1i−1∑y=0j−vfv,x,ygi−x,j−y−vPv+1x(i−x)(i−1x−1)f _ {v, i, j} = g _ {v, i, j} - \sum\limits _ {x = 1} ^ {i - 1} \sum\limits _ {y = 0} ^ {j - v} f _ {v, x, y} g _ {i - x, j - y - v} P _ {v + 1} ^ {x(i - x)} \binom{i - 1}{x - 1}

其中 Pi=p0+∑j=ikpjP _ i = p _ 0 + \sum _ {j = i} ^ k p _ j。

也就是枚举大小后，这个连通块与其他点无边则视为用 vv 边连接。

同理：

gv,i,j=fv−1,i,j+∑x=1i−1∑y=0j−vfv−1,x,ygi−x,j−y−vPvx(i−x)(i−1x−1)g _ {v, i, j} = f _ {v - 1, i, j} + \sum\limits _ {x = 1} ^ {i - 1} \sum\limits _ {y = 0} ^ {j - v} f _ {v - 1, x, y} g _ {i - x, j - y - v} P _ v ^ {x(i - x)} \binom{i - 1}{x - 1}

最终答案就是 fk,nf _ {k, n}。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 1e9 + 7, inv100 = 570000004;

int n, k, p[15];
int pw[15][785], C[785][785], f[55][205], g[55][205];

int main() {
	freopen("mst.in", "r", stdin);
	freopen("mst.out", "w", stdout);
	scanf("%d%d", &n, &k);
	for (int i = 0; i <= k; i++) scanf("%d", &p[i]), p[i] = (long long)p[i] * inv100 % mod;
	p[k + 1] = p[0];
	for (int i = k; i >= 1; i--) p[i] = (p[i] + p[i + 1]) % mod;
	for (int i = 1; i <= k + 1; i++) {
		pw[i][0] = 1;
		for (int j = 1; j <= n * (n - 1) / 2; j++) pw[i][j] = (long long)pw[i][j - 1] * p[i] % mod;
	}
	for (int i = 0; i <= n * (n - 1) / 2; i++)
		for (int j = 0; j <= i; j++)
			if (j == 0 || j == i) C[i][j] = 1;
			else C[i][j] = (C[i - 1][j - 1] + C[i - 1][j]) % mod;
	f[1][0] = 1;
	for (int t = 1; t <= k; t++) {
		memset(g, 0, sizeof(g));
		for (int i = 1; i <= n; i++)
			for (int j = 0; j <= (i - 1) * t; j++) {
				g[i][j] = f[i][j];
				for (int x = 1; x < i; x++)
					for (int y = 0; y + t <= j; y++)
						g[i][j] = (g[i][j] +
							(long long)f[x][y] * g[i - x][j - y - t] % mod * pw[t][x * (i - x)] % mod *
							C[i - 1][x - 1]) % mod;
			}
		memset(f, 0, sizeof(f));
		for (int i = 1; i <= n; i++)
			for (int j = 0; j <= (i - 1) * t; j++) {
				f[i][j] = g[i][j];
				for (int x = 1; x < i; x++)
					for (int y = 0; y + t <= j; y++)
						f[i][j] = (f[i][j] + mod -
							((long long)f[x][y] * g[i - x][j - y - t] % mod * pw[t + 1][x * (i - x)] % mod *
							C[i - 1][x - 1] % mod)) % mod;
			}
	}
	for (int i = n - 1; i <= k * (n - 1); i++) printf("%d ", f[n][i]);
	puts("");
	return 0;
}

3.23

TopCoder TreeCount

给定一棵树，定义 kk - 独立集是一个点集满足集合内的点只有最多 kk 个与之相邻的点在集合内。求 k=0∼n−1k = 0 \sim n - 1 时 kk - 独立集的数量。

设 dpu,i,jdp _ {u, i, j} 表示 uu 子树 uu 有 ii 个儿子在集合内时 jj - 独立集的数量，特别地 i=−1i = -1 表示 uu 不在集合内。直接转移即可。

TopCoder CheckerFreeness

给定 nn 个点，每个点为黑色或白色，问是否存在凸四边形使得相邻点不同色。

找出所有端点均为白色的线段和均为黑色的线段，若存在白线段与黑线段有交则存在这样的凸四边形，否则不存在。

暴力卡卡常过了。

或者考虑两条中必然有一条在其中一种颜色的凸包上就可以优化到 O(n3)O(n ^ 3)。

TopCoder CharacterBoard

懒得写题面了。

考虑对于一个确定的长度计算方案数是简单的，然后如果这个长度的字符串在子矩形中有一个位置出现了两次，则长度必然是 iW+ji W + j 的因数，其中 i∈[0,n+1],j∈[−m,m]i \in [0, n + 1], j \in [-m, m]。找出这些暴力 check，然后剩下的若长度为 lenlen 则方案数为 26len−nm26 ^ {len - nm}，等比数列求和即可。

TopCoder RandomPaintingOnABoard

一个 n×mn \times m 的网格，刚开始全是白色，每次按某种确定的概率给某个格子染黑，可以重复染色，问使每行每列至少一个黑色的期望次数。

暴力就是 min-max 容斥，然后考虑对行 min-max 容斥，对列可以直接 DP。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, m, a[25][25], b[25][25], sum;
double ans;
int dp[25][2][1355];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		m = s.length();
		for (int j = 1; j <= m; j++)
			a[i][j] = s[j - 1] - '0', sum += a[i][j];
	}
	if (n > m) {
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++) b[j][i] = a[i][j];
		memcpy(a, b, sizeof(a));
		swap(n, m);
	}
	for (int S = 0; S < 1 << n; S++) {
		int pre = 0;
		for (int i = 1; i <= n; i++)
			if (S >> (i - 1) & 1)
				for (int j = 1; j <= m; j++) pre += a[i][j];
		memset(dp, 0, sizeof(dp));
		dp[0][__builtin_popcount(S) & 1][pre] = 1;
		// dp[0][0][0] = 1;
		for (int i = 1; i <= m; i++) {
			int s = 0;
			for (int j = 1; j <= n; j++)
				if (!(S >> (j - 1) & 1)) s += a[j][i];
			// if (S == 0 && i == 1) eprintf("s = %d\n", s);
			for (int j = 0; j <= 9 * n * m; j++) {
				dp[i][0][j] = dp[i - 1][0][j];
				if (j >= s) dp[i][0][j] += dp[i - 1][1][j - s];
				dp[i][1][j] = dp[i - 1][1][j];
				if (j >= s) dp[i][1][j] += dp[i - 1][0][j - s];
			}
		}
		// eprintf("de: %d %d\n", S, dp[1][1][8]);
		double res = 0;
		for (int i = 1; i <= 9 * n * m; i++) {
			// eprintf("%d %d %d %d\n", S, i, dp[m][1][i], dp[m][0][i]);
			res += dp[m][1][i] * (double)sum / i;
			res -= dp[m][0][i] * (double)sum / i;
		}
		ans += res;
		// eprintf("%d %lf\n", S, res);
	}
	printf("%.15lf\n", ans);
	return 0;
}

3.25

TopCoder TreeUnion

给定两棵 nn 个点的树，等概率随机一个长度为 nn 的排列 PP，第一棵树的点 ii 与第二课树的点 PiP_i 连边，求图中长度为 KK 的环的数量的期望。

K≤7K \le 7。

发现 K≤7K \le 7 的时候环只会是两棵树各一条链，所以两边树形 DP 数某个长度的链的数量然后合并就好了。

TopCoder CentaurCompany

有一棵 nn 个点的树，每个点等概率划分到 AA 集合或 BB 集合，然后每个集合分别求出导出子图后再进行连边，每个点可以免费连一条边，其余边需要 11 的费用，问使两张图都连通的最小代价的期望。

对于每张图，设连通块数为 ii，点数为 jj，则代价显然是 2i−2−j2i-2-j，设 dpu,0/1,i,jdp_{u,0/1,i,j} 表示 uu 子树，选或没选 uu，ii 个连通块，jj 个点的方案数，直接 DP 即可。

TopCoder NumberLabyrinthDiv1

笛卡尔平面第一象限和 x 轴，y 轴的正半轴是一个棋盘，已经有若干个点，点 (x,y)(x, y) 上的数 dd 表示可以走到 (x−d,y−d),(x−d,y+d),(x+d,y−d),(x+d,y+d)(x-d,y-d), (x-d,y+d), (x+d,y-d), (x+d,y+d)，你要再放 kk 个点，从 (0,0)(0,0) 走到 (n,m)(n,m)，问路径最短的路径数量。

保证已有的点在第一象限上。

发现 k≤1k \le 1 的时候无解，k≥2k \ge 2 时最短路长度为 n+mn+m，因此只会往右或往上走。直接 DP，唯一的问题就是求出从某个已有点到另一个已有点，用 kk 个点，不经过其他已有点的最小代价。

考虑容斥，首先不考虑其他已有点，设要走 (n,m)(n, m)，枚举有多少个点向上走，剩下的向右走，然后插板即可。

考虑已有点就是枚举第一个走到的已有点，直接来就行。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 1e9 + 9;

int n, tx, ty, m, cnt[45][45][15], fac[1000005], inv[1000005], dp[45][15];
struct node {int x, y, d;} a[45];

int C(int n, int m) {return n >= m ? (long long)fac[n] * inv[m] % mod * inv[n - m] % mod : 0;}
int calc(int x, int y, int k) {
	if (x < 0 || y < 0) return 0;
	if (!x && !y) return !k;
	if (!k) return 0;
	if (!x) return C(y - 1 , k - 1);
	if (!y) return C(x - 1 , k - 1);
	int res = 0;
	for (int i = 1; i < k; i++)
		res = (res + (long long)C(k, i) * C(x - 1, i - 1) % mod * C(y - 1, k - i - 1)) % mod;
	// eprintf("calc(%d, %d, %d) = %d\n", x, y, k, res);
	return res;
}

int main() {
	fac[0] = fac[1] = 1;
	inv[0] = inv[1] = 1;
	for (int i = 2; i <= 1000000; i++) {
		fac[i] = (long long)fac[i - 1] * i % mod;
		inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
	}
	for (int i = 2; i <= 1000000; i++) inv[i] = (long long)inv[i] * inv[i - 1] % mod;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i].x);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i].y);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i].d);
	scanf("%d%d%d", &tx, &ty, &m);
	a[++n] = {0, 0, 0};
	sort(a + 1, a + n + 1, [](const node &u, const node &v) {
		return u.x != v.x ? u.x < v.x : u.y < v.y;
	});
	while (a[n].x > tx || a[n].y > ty) n--;
	if (a[n].x != tx || a[n].y != ty) a[++n] = {tx, ty, 0};
	// eprintf("%d\n", n);
	for (int i = 1; i <= n; i++)
		for (int j = i + 1; j <= n; j++)
			for (int k = 0; k <= m; k++) {
				cnt[i][j][k] = calc(a[j].x - a[i].x - a[i].d, a[j].y - a[i].y, k);
				if (a[i].d)
					cnt[i][j][k] = (cnt[i][j][k] + calc(a[j].x - a[i].x, a[j].y - a[i].y - a[i].d, k)) % mod;
				for (int l = i + 1; l < j; l++)
					for (int t = 0; t <= k; t++)
						cnt[i][j][k] = (cnt[i][j][k] + mod -
							(long long)cnt[i][l][t] * calc(a[j].x - a[l].x, a[j].y - a[l].y, k - t) %
							mod) % mod;
			}
	dp[1][0] = 1;
	for (int i = 2; i <= n; i++)
		for (int j = 1; j < i; j++)
			for (int k = 0; k <= m; k++)
				for (int t = 0; t <= k; t++)
					dp[i][k] = (dp[i][k] + (long long)dp[j][t] * cnt[j][i][k - t]) % mod;
	// eprintf("%d\n", cnt[1][2][2]);
	int ans = 0;
	for (int i = 0; i <= m; i++) ans = (ans + dp[n][i]) % mod;
	printf("%d\n", ans);
	return 0;
}

TopCoder WallGameDiv1

两个人在一个网格上玩游戏，(i,j)(i,j) 上有数字 ai,ja_{i,j}。A 先把棋子放在第一行的某个位置，然后每次 B 选择任意对上下相邻的格子在中间放一堵墙，A 再移动棋子，棋子可以左右下移动，不能穿过墙，B 放墙要保证 A 能到达最后一行，到达最后一行时游戏立即结束，分数是棋子经过的网格的数字之和，重复经过多次计算，A 要时分数最小，B 要使分数最大，求最终分数。

显然 B 在需要的时候再放墙，因此每层墙都是一个区间或留下一个洞，设 fi,l,r,0/1f_{i,l,r,0/1} 表示在第 ii 层，墙堵上了 [l,r][l,r]，棋子在 ll 或 rr 时的答案，直接 DP 即可。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, m, a[55][55], dp[55][55][55][2];

int main() {
	scanf("%d", &n);
	for(int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		m = s.length();
		s = " " + s;
		for (int j = 1; j <= m; j++) a[i][j] = s[j] - '0' + a[i][j - 1];
	}
	if (m == 1) {
		int ans = 0;
		for (int i = 1; i <= n; i++) ans += a[i][1];
		printf("%d\n", ans);
		return 0;
	}
	memset(dp, 0x3f, sizeof(dp));
	for (int i = 1; i <= m; i++) dp[n][i][i][0] = dp[n][i][i][1] = 0;
	for (int i = n - 1; i >= 1; i--) {
		dp[i][1][m][0] = dp[i][1][m][1] = 0;
		for (int len = m - 1; len >= 1; len--)
			for (int l = 1; l + len - 1 <= m; l++) {
				int r = l + len - 1;
				if (l > 1) {
					int v = max(dp[i][l - 1][r][0],
						dp[i + 1][l - 1][l - 1][0] + a[i + 1][l - 1] - a[i + 1][l - 2]);
					dp[i][l][r][0] = min(dp[i][l][r][0], v + a[i][l - 1] - a[i][l - 2]);
					dp[i][l][r][1] = min(dp[i][l][r][1], v + a[i][r - 1] - a[i][l - 2]);
				}
				if (r < m) {
					int v = max(dp[i][l][r + 1][1],
						dp[i + 1][r + 1][r + 1][1] + a[i + 1][r + 1] - a[i + 1][r]);
					dp[i][l][r][0] = min(dp[i][l][r][0], v + a[i][r + 1] - a[i][l]);
					// if (i == 1 && l == 1 && r == 4) eprintf("%d\n", dp[2][5][5][1]);
					dp[i][l][r][1] = min(dp[i][l][r][1], v + a[i][r + 1] - a[i][r]);
				}
				if (l == r) {
					dp[i][l][r][0] = max(dp[i][l][r][0], dp[i + 1][l][r][0] + a[i + 1][l] - a[i + 1][l - 1]);
					dp[i][l][r][1] = max(dp[i][l][r][1], dp[i + 1][l][r][1] + a[i + 1][r] - a[i + 1][r - 1]);
				}
			}
	}
	// eprintf("%d\n", dp[3][1][1][0]);
	int ans = 0x3f3f3f3f;
	for (int i = 1; i <= m; i++) ans = min(ans, dp[1][i][i][0] + a[1][i] - a[1][i - 1]);
	printf("%d\n", ans);
	return 0;
}

TopCoder CandyOnDisk

平面上有 nn 个圆，给出起点和终点，每次可以选择某个圆，移动到与该圆圆心距离相同的某个点，要求当时在这个圆内，求能否走到终点。

发现若能从某个圆走到另一个圆，则两圆的交和这些点在两个圆上构成的圆环都是能走到的，因此暴力枚举连边维护连通性即可。

3.26

发现每题都记太浪费时间了，所以下面就只记有意义的题。

TopCoder EqualSums

给定 n×nn \times n 的矩阵，只有一些位置已确定，在空白格上填非负整数，使得对于任意两个 p,qp, q，∑i=1nai,pi=∑i=1nai,qi\sum_{i=1}^n a_{i,p_i} = \sum_{i=1}^n a_{i,q_i}。

矩阵合法当且仅当存在两个序列 b,cb, c 使得 ai,j=bi+cja_{i,j} = b_i+c_j。

然后用带权并查集维护连通块，再设 dpi,j,kdp_{i,j,k} 表示钦定前 ii 个连通块，行的最小值是 jj，列的最小值是 kk 的方案数，每次枚举填的数转移。为了保证不重复计算矩形，只要钦定列的最小值是 00 就行了。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <cmath>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 1e9 + 7;

int n, ans = 1, a[55][55], dp[105][15][15], val[105];
vector<pair<int, int>> g[105];
struct dsu {
	int fa[105];

	dsu() {for (int i = 1; i < 105; i++) fa[i] = i;}
	int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
	void merge(int x, int y) {fa[find(x)] = find(y); return ;}
} d;

void dfs(int now, int v, int &vr, int &vc) {
	val[now] = v;
	if (now <= n) vr = min(vr, val[now]);
	else vc = min(vc, val[now]);
	for (auto i : g[now])
		if (val[i.first] == -1) dfs(i.first, i.second - val[now], vr, vc);
	return ;
}

int main() {
	scanf("%d", &n);
	memset(a, -1, sizeof(a));
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		s = " " + s;
		for (int j = 1; j <= n; j++)
			if (s[j] != '-') {
				d.merge(i, n + j);
				a[i][j] = s[j] - '0';
				g[i].emplace_back(n + j, a[i][j]);
				g[n + j].emplace_back(i, a[i][j]);
			}
	}
	dp[0][10][10] = 1;
	for (int i = 1; i <= 2 * n; i++)
		if (d.find(i) == i) {
			for (int v = 0; v <= 10; v++) {
				int vr = 0x3f3f3f3f, vc = 0x3f3f3f3f;
				memset(val, -1, sizeof(val));
				dfs(i, v, vr, vc);
				// eprintf("%d %d %d %d\n", i, v, vr, vc);
				if (vr < 0 || vc < 0) continue;
				int flag = 1;
				for (int j = 1; j <= n; j++) if (val[j] != -1)
					for (int k = 1; k <= n; k++) if (val[n + k] != -1)
						if (a[j][k] != -1 && val[j] + val[n + k] != a[j][k]) {flag = 0; break;}
				if (!flag) continue;
				for (int j = 0; j <= 10; j++)
					for (int k = 0; k <= 10; k++)
						dp[i][min(vr, j)][min(vc, k)] =
							(dp[i][min(vr, j)][min(vc, k)] + dp[i - 1][j][k]) % mod;
			}
		} else memcpy(dp[i], dp[i - 1], sizeof(dp[i]));
	int ans = dp[2 * n][0][0];
	for (int j = 1; j <= 10; j++) ans = (ans + dp[2 * n][j][0]) % mod;
	printf("%d\n", ans);
	return 0;
}

TopCoder SimilarNames

给定 nn 个字符串，要进行重标号，满足 mm 条限制，其中每条限制形如 ii 是 jj 的前缀。求方案数。

建出 Trie，暴力就是设 dpi,Sdp_{i,S} 表示 ii 子树确定了 SS 内的点的标号的方案数，SS 只须记录有限制的点，暴力子集卷积转移复杂度是 O(n32m)O(n3^{2m})。

发现若一个点只有入边没有出边则可以直接挂在入点上，添加一个点的同时数挂在他上面的点的方案数，这样点数只剩 3m2\frac{3m}{2} 了。

以上是考场做法，有点太保守了。发现只需要保留有出边的点，对于只有入边的点，当入点集合全被加进去时统计他的方案数即可。

3.29

A

给一张图，求打小为 44 的团的数量。

考虑三元环计数，按度数从小到大排序分析，可以发现每个点只有 O(m)O(\sqrt{m}) 条出边，暴力 bitset 合并即可做到 O(m2ω)O(\frac{m^2}{\omega})。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <vector>
#include <bitset>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, m, deg[100005], p[100005], q[100005], vis[100005], id[100005];
struct edge {int u, v;} e[100005];
vector<int> g[100005];
bitset<705> b[100005];

int main() {
	freopen("kfour.in", "r", stdin);
	freopen("kfour.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin >> n >> m;
	for (int i = 1; i <= m; i++) cin >> e[i].u >> e[i].v, deg[e[i].u]++, deg[e[i].v]++;
	for (int i = 1; i <= n; i++) p[i] = i;
	sort(p + 1, p + n + 1, [](const int &x, const int &y) {
		return deg[x] < deg[y] || (deg[x] == deg[y] && x < y);
	});
	for (int i = 1; i <= n; i++) q[p[i]] = i;
	for (int i = 1; i <= m; i++)
		if (q[e[i].u] < q[e[i].v]) g[e[i].u].push_back(e[i].v);
		else g[e[i].v].push_back(e[i].u);
	for (int i = 1; i <= n; i++)
		sort(g[i].begin(), g[i].end(), [](const int &x, const int &y) {return q[x] < q[y];});
	long long ans = 0;
	for (int i = 1; i <= n; i++) {
		int idx = 0;
		for (int j : g[i]) vis[j] = 1, id[j] = ++idx;
		for (int j : g[i])
			for (int k : g[j])
				if (vis[k]) b[j][id[k]] = 1;
		for (int j : g[i])
			for (int k : g[j])
				if (vis[k]) ans += (b[j] & b[k]).count();
		for (int j : g[i]) vis[j] = 0, b[j].reset();
	}
	cout << "0 0 0 " << ans << '\n';
	return 0;
}

B

给你一个序列，求本值不同子序列数量，其中子序列不同当且仅当长度不同或和不同。保证 11 的个数不少于总和的 15\frac{1}{5}。

朴素暴力是设 fi,jf_{i,j} 表示长度为 ii 和为 jj 是否可行，发现若一种方案没有用 11 则 (i,j)(i,j) 可行那么对于 kk 小于等于 11 的个数，(i+k,j+k)(i+k,j+k) 也可行。旋转 π4\frac{\pi}{4} ，状态改成 fj−i,jf_{j-i,j}，就变成了区间，显然只有 O(1)O(1) 段区间，直接转移即可。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int O = 200000;

int n, S, a[200005], le, ri;
vector<pair<int, int>> dp[400005];
long long ans;

void update(vector<pair<int, int>> &vec, vector<pair<int, int>> &from, int delta) {
	vector<pair<int, int>> tmp;
	tmp.swap(vec);
	for (auto i : from) tmp.emplace_back(i.first + delta, i.second + delta);
	sort(tmp.begin(), tmp.end());
	for (auto i : tmp)
		if (vec.empty() || vec.back().second < i.first) vec.push_back(i);
		else if (i.second > vec.back().second) vec.back().second = i.second;
	return ;
}
void solve(int dx, int dy) {
	if (dx > 0) {
		for (int i = ri; i >= le; i--) update(dp[i + dx], dp[i], dy);
		ri += dx;
	} else {
		for (int i = le; i <= ri; i++) update(dp[i + dx], dp[i], dy);
		le += dx;
	}
	return ;
}

int main() {
	freopen("skew.in", "r", stdin);
	freopen("skew.out", "w", stdout);
	scanf("%d%d", &n, &S);
	for (int i = 1; i <= n; i++) {
		int x;
		scanf("%d", &x);
		a[x]++;
	}
	dp[le = ri = O].emplace_back(0, a[1]);
	for (int i = 0; i <= S; i++)
		if (i != 1 && a[i]) {
			for (int j = 1; j <= a[i]; j <<= 1) solve((i - 1) * j, i * j), a[i] -= j;
			if (a[i]) solve((i - 1) * a[i], i * a[i]);
		}
	for (int i = le; i <= ri; i++)
		for (auto j : dp[i]) ans += j.second - j.first + 1;
	printf("%lld\n", ans);
	return 0;
}

3.30

TopCoder BearGirls

懒得写题面了。

设 fi,jf_{i,j} 为前 ii 个，第 ii 个人在前 ii 个中排名为 jj 时的答案，gi,jg_{i,j} 为随机 ii 个，排名为 jj 的人的期望大小。

fi,j=max⁡{gi,j,1i+1∑k=1i+1fi+1,k−c}gi,j=ji+1gi+1,j+1+i+1−ji+1gi+1,jf_{i,j} = \max\left\{g_{i,j}, \frac{1}{i+1} \sum\limits_{k=1}^{i+1} f_{i+1,k}-c\right\} \\ g_{i,j} = \frac{j}{i+1} g_{i+1,j+1} + \frac{i+1-j}{i+1} g_{i+1,j}

边界是 fn,i=gn,i=aif_{n,i} = g_{n,i} = a_i，答案为 f1,1−cf_{1,1}-c。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, c, b[105], a[10005];
double f[10005], g[10005];

int main() {
	int _n;
	scanf("%d", &_n);
	for (int i = 1; i <= _n; i++) scanf("%d", &b[i]);
	scanf("%d", &_n);
	for (int i = 1; i <= _n; i++) {
		int t;
		scanf("%d", &t);
		for (int j = b[i]; j < b[i] + t; j++) a[++n] = j;
	}
	scanf("%d", &c);
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) f[i] = g[i] = a[i];
	for (int i = n - 1; i >= 1; i--) {
		double sum = 0;
		for (int j = 1; j <= i + 1; j++) sum += f[j];
		for (int j = 1; j <= i; j++) {
			g[j] = g[j + 1] * j / (i + 1) + g[j] * (i + 1 - j) / (i + 1);
			f[j] = max(g[j], sum / (i + 1) - c);
		}
	}
	printf("%.15lf\n", f[1] - c);
	return 0;
}

4.1

TopCoder PointErasing

平面上有 nn 个点 (i,yi)(i, y_i)，每次选择两个点并移除严格在矩形内的点 ，知道无法移除点，问最终状态的点数的方案数。

容易发现最大值、最小值、第一个点和最后一个点一定无法删除。

然后用这些点可以删除所有不等于最大值、最小值、第一个点和最后一个点的数。

接着考虑最大最小值的第一个和最后一个，发现把图切割成了左右两部分，容易发现左边只留下与第一个相等的，右边只留下与最后一个相等的。并且容易证明左右两边不会互相影响，因此只要做一边然后暴力合并就好了。

首先暴力求出所有可行的区间，然后容易调整证明操作区间不会相交，因此设 dpi,jdp_{i, j} 表示前 ii 个数剩 jj 个是否可能，直接枚举区间然后 bitset 优化即可。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <vector>
#include <bitset>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, a[55], mx, mn = 0x3f3f3f3f, L = 0x3f3f3f3f, R, cnt;
bitset<55> dp[55], dpl, dpr;
vector<int> ans;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]), mx = max(mx, a[i]), mn = min(mn, a[i]);
	for (int i = 1; i <= n; i++)
		if (a[i] == mn || a[i] == mx) L = min(L, i), R = max(R, i), cnt++;
	dp[0][0] = 1;
	for (int i = 1; i < L; i++)
		if (a[i] == a[1]) dp[i] = dp[i - 1] << 1;
		else {
			dp[i] = dp[i - 1];
			for (int j = 1; j < i; j++)
				if (a[j] != a[1] && (a[j] < a[1]) != (a[i] < a[1])) dp[i] |= dp[j];
		}
	dpl = dp[L - 1];
	for (int i = 1; i < L; i++)
		if (a[i] != a[1]) dpl |= dp[i];
	dp[n + 1][0] = 1;
	for (int i = n; i >= R; i--)
		if (a[i] == a[n]) dp[i] = dp[i + 1] << 1;
		else {
			dp[i] = dp[i + 1];
			for (int j = n; j > i; j--)
				if (a[j] != a[n] && (a[j] < a[n]) != (a[i] < a[n])) dp[i] |= dp[j];
		}
	dpr = dp[R + 1];
	for (int i = n; i > R; i--)
		if (a[i] != a[n]) dpr |= dp[i];
	// eprintf("%d\n", cnt);
	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			if (dpl[i] && dpr[j]) ans.push_back(i + j + cnt);
	sort(ans.begin(), ans.end());
	ans.erase(unique(ans.begin(), ans.end()), ans.end());
	for (int i : ans) printf("%d ", i);
	puts("");
	return 0;
}

TopCoder XorLife

生命游戏，给你初始局面，每次四连桶和自己五个点有奇数个活着时则下一时刻活，否则死，问 kk 秒后活着几个。

考虑两秒后的情况，发现 (x,y)(x, y) 取决于 (x,y),(x−2,y),(x,y−2),(x+2,y),(x,y+2)(x, y), (x - 2, y), (x, y - 2), (x + 2, y), (x, y + 2)，因此 kk 是偶数时直接切成四份递归，否则暴力做一次，然后记忆化。

时间复杂度不会分析……

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <map>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int gx[] = {0, 1, -1, 0, 0}, gy[] = {0, 0, 0, -1, 1};

int n;
vector<vector<int>> a;
int k;
map<pair<vector<vector<int>>, int>, long long> mp;

long long dfs(vector<vector<int>> a, int k) {
	// for (vector<int> i : a) {
	// 	for (int j : i) eprintf("%d", j);
	// 	eputs("");
	// }
	// eprintf("%d\n", k);
	if (mp.count({a, k})) return mp[{a, k}];
	int n = a.size(), m = a[0].size();
	int sum = 0;
	for (vector<int> i : a)
		for (int j : i) sum += j;
	if (!k) return mp[{a, k}] = sum;
	if (!sum) return 0;
	if (k % 2) {
		vector<vector<int>> b(n + 2);
		for (int i = 0; i < n + 2; i++) {
			b[i].resize(m + 2);
			for (int j = 0; j < m + 2; j++) {
				int s = 0;
				for (int k = 0; k < 5; k++) {
					int x = i + gx[k] - 1, y = j + gy[k] - 1;
					if (x < 0 || x >= n || y < 0 || y >= m) continue;
					s += a[x][y];
				}
				b[i][j] = s % 2;
			}
		}
		return mp[{a, k}] = dfs(b, k - 1);
	}
	long long res = 0;
	for (int i = 0; i < min(n, 2); i++)
		for (int j = 0; j < min(m, 2); j++) {
			vector<vector<int>> b((n - i + 1) / 2, vector<int>((m - j + 1) / 2));
			for (int x = i; x < n; x += 2)
				for (int y = j; y < m; y += 2) b[x / 2][y / 2] = a[x][y];
			res += dfs(b, k / 2);
		}
	return mp[{a, k}] = res;
}

int main() {
	scanf("%d", &n);
	a.resize(n);
	for (int i = 0; i < n; i++) {
		string s;
		cin >> s;
		a[i].resize(s.length());
		for (int j = 0; j < (int)s.length(); j++) a[i][j] = s[j] == 'o';
	}
	scanf("%d", &k);
	printf("%lld\n", dfs(a, k));
	return 0;
}

TopCoder ElephantDrinking

n×nn \times n 的网格，每个格子有一个权值，从四个边界伸出 4n4n 根木棍，不能相交，问被覆盖的格子的权值和的最大值。

分讨，一种是行左侧最大值和行右侧最大值不交，这种情况枚举两侧最大值。


这样切成五部分。

另一种是相交，会按以下两种情况划分成四部分：

也直接枚举中间没被取到的情况。

然后就 DP 求包含四个角的子矩形的答案和某些行区间的答案和某些列区间的答案即可。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, m, a[55][55];
int ul[55][55], ur[55][55], dl[55][55], dr[55][55];
int row[55][55], col[55][55];
int ans;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		m = s.length();
		for (int j = 1; j <= m; j++) a[i][j] = s[j - 1] - '0';
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++) {
			ul[i][j] = max(ul[i - 1][j] + a[i][j], ul[i][j - 1] + a[i][j]);
			for (int k = 1; k <= j; k++) ul[i][j] = max(ul[i][j], ul[i - 1][j] + a[i][k]);
			for (int k = 1; k <= i; k++) ul[i][j] = max(ul[i][j], ul[i][j - 1] + a[k][j]);
		}
	for (int i = 1; i <= n; i++)
		for (int j = m; j >= 1; j--) {
			ur[i][j] = max(ur[i - 1][j] + a[i][j], ur[i][j + 1] + a[i][j]);
			for (int k = m; k >= j; k--) ur[i][j] = max(ur[i][j], ur[i - 1][j] + a[i][k]);
			for (int k = 1; k <= i; k++) ur[i][j] = max(ur[i][j], ur[i][j + 1] + a[k][j]);
		}
	// eprintf("%d\n", ur[3][3]);
	for (int i = n; i >= 1; i--)
		for (int j = 1; j <= m; j++) {
			dl[i][j] = max(dl[i + 1][j] + a[i][j], dl[i][j - 1] + a[i][j]);
			for (int k = 1; k <= j; k++) dl[i][j] = max(dl[i][j], dl[i + 1][j] + a[i][k]);
			for (int k = n; k >= i; k--) dl[i][j] = max(dl[i][j], dl[i][j - 1] + a[k][j]);
		}
	for (int i = n; i >= 1; i--)
		for (int j = m; j >= 1; j--) {
			dr[i][j] = max(dr[i + 1][j] + a[i][j], dr[i][j + 1] + a[i][j]);
			for (int k = m; k >= j; k--) dr[i][j] = max(dr[i][j], dr[i + 1][j] + a[i][k]);
			for (int k = n; k >= i; k--) dr[i][j] = max(dr[i][j], dr[i][j + 1] + a[k][j]);
		}
	for (int l = 1; l <= n; l++)
		for (int r = l; r <= n; r++) {
			row[l][r] = row[l][r - 1];
			int mx1 = 0, mx2 = 0;
			for (int k = 1; k <= m; k++)
				if (a[r][k] >= mx1) mx2 = mx1, mx1 = a[r][k];
				else if (a[r][k] >= mx2) mx2 = a[r][k];
			row[l][r] += mx1 + mx2;
		}
	for (int l = 1; l <= m; l++)
		for (int r = l; r <= m; r++) {
			col[l][r] = col[l][r - 1];
			int mx1 = 0, mx2 = 0;
			for (int k = 1; k <= n; k++)
				if (a[k][r] >= mx1) mx2 = mx1, mx1 = a[k][r];
				else if (a[k][r] >= mx2) mx2 = a[k][r];
			col[l][r] += mx1 + mx2;
		}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= n; j++)
			for (int p = 1; p <= m; p++)
				for (int q = m; q > p; q--) {
					ans = max(ans,
						a[i][p] + a[j][q] +
						ul[i - 1][p] + ur[j - 1][q] + dl[i + 1][p] + dr[j + 1][q] +
						col[p + 1][q - 1]);
				}
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= m; j++)
			for (int p = 1; p <= n; p++)
				for (int q = n; q > p; q--)
					ans = max(ans,
						a[p][i] + a[q][j] +
						ul[p][i - 1] + dl[q][j - 1] + ur[p][i + 1] + dr[q][j + 1] +
						row[p + 1][q - 1]);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= m; j++)
			for (int p = i; p <= n; p++)
				for (int q = j; q <= m; q++) {
					ans = max(ans, ul[i - 1][q] + ur[p][q + 1] + dl[i][j - 1] + dr[p + 1][j]);
					ans = max(ans, ul[p][j - 1] + ur[i - 1][j] + dl[p + 1][q] + dr[i][q + 1]);
				}
	printf("%d\n", ans);
	return 0;
}

4.2

TopCoder RockPaperScissors

先咕着……

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, cnt[55][3];
double f[55][55][55], g[55][55][55], p[55][55][55][3];
double ans;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &cnt[i][0]);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &cnt[i][1]);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &cnt[i][2]);
	f[0][0][0] = 1;
	for (int i = 1; i <= n; i++) {
		memcpy(g, f, sizeof(g));
		for (int x = 0; x <= i; x++)
			for (int y = 0; y <= i - x; y++)
				for (int z = 0; z <= i - x - y; z++) {
					if (x)
						f[x][y][z] += g[x - 1][y][z] * (x + y + z) * cnt[i][0] / 300. / (n - x - y - z + 1);
					if (y)
						f[x][y][z] += g[x][y - 1][z] * (x + y + z) * cnt[i][1] / 300. / (n - x - y - z + 1);
					if (z)
						f[x][y][z] += g[x][y][z - 1] * (x + y + z) * cnt[i][2] / 300. / (n - x - y - z + 1);
				}
	}
	// eprintf("%lf\n", f[2][0][0]);
	for (int x = 0; x <= n; x++)
		for (int y = 0; y <= n - x; y++)
			for (int z = 0; z <= n - x - y; z++) {
				if (x) p[x - 1][y][z][0] = f[x][y][z] * x / (x + y + z);
				if (y) p[x][y - 1][z][1] = f[x][y][z] * y / (x + y + z);
				if (z) p[x][y][z - 1][2] = f[x][y][z] * z / (x + y + z);
			}
	for (int x = 0; x < n; x++)
		for (int y = 0; y < n - x; y++)
			for (int z = 0; z < n - x - y; z++) {
				double res = 0;
				for (int i = 0; i < 3; i++) res = max(res, p[x][y][z][i] * 3 + p[x][y][z][(i + 1) % 3]);
				// eprintf("%d %d %d %lf\n", x, y, z, res);
				ans += res;
			}
	printf("%.12lf\n", ans);
	return 0;
}
/*
2
100 100
2
100 100
2
100 100
*/

4.5

B

给定 nn 和 xx，问长度为 nn 的排列 pp，钦定 px=1∼np_x = 1\sim n 时笛卡尔树不同的排列个数。

令 y=pxy = p_x。

相当于要求 sizx≤n+1−y,depx≤ysiz_x \le n + 1 - y, dep_x \le y。

y=1y = 1 时答案显然为 Hx−1Hn−xH_{x - 1} H_{n - x}，其中 HH 为卡特兰数。

y=iy = i 的答案为 y=i−1y = i - 1 的答案减去 sizx=n+1−(i−1)siz_x = n + 1 - (i - 1) 的答案加上 depx=idep_x = i 的答案，然后就是分别求这两个东西。

求 depx=ydep_x = y 的方案：枚举 [1,x−1][1, x - 1] 和 [x+1,n][x + 1, n] 中分别有 pp 和 qq 个是 xx 的祖先，合并的方案数为 (p+qp)\binom{p + q}{p}。然后考虑两边分别的方案数，以左边为例，就是 xx 个点的笛卡尔树，最后一个点深度为 p+1p + 1。映射到括号序后可以得到答案为 p+1x(2x−p−2x−p−1)\frac{p + 1}{x}\binom{2x - p - 2}{x - p - 1}。用 EGF 卷起来即可。

求 sizx=ysiz_x = y 的方案：枚举 xx 的子树为 [x−l,x+r][x - l, x + r]， 合并的方案数为 HlHrH_l H_r，然后把这段缩成一个点，剩下 n−l−rn - l - r 个点，要求 x−lx - l 是叶子。发现删掉 x−lx - l 后构造笛卡尔树，x−lx - l 的位置是唯一确定的，因此方案数为 Hn−l−r−1H_{n - l - r - 1}。用 OGF 卷起来即可。

然后就做完了。

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
105
106
107
108
109
110
111
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

namespace Poly {
	const int mod = 998244353, G = 3, invG = 332748118;

	int power(int a, int b) {
		int ans = 1;
		while (b) {
			if (b & 1) ans = (long long)ans * a % mod;
			a = (long long)a * a % mod;
			b >>= 1;
		}
		return ans % mod;
	}

	struct poly: vector<int> {
		template<typename ... argT>
		poly(argT &&... args): vector<int>(forward<argT>(args)...) {}

		void NTT(poly &g, int flag) const {
			int n = g.size();
			vector<unsigned long long> f(g.begin(), g.end());
			vector<int> swp(n);
			for (int i = 0; i < n; i++) {
				swp[i] = swp[i >> 1] >> 1 | ((i & 1) * (n >> 1));
				if (i < swp[i]) std::swap(f[i], f[swp[i]]);
			}
			for (int mid = 1; mid < n; mid <<= 1) {
				int w1 = power(flag ? G : invG, (mod - 1) / mid / 2);
				vector<int> w(mid);
				w[0] = 1;
				for (int i = 1; i < mid; i++) w[i] = (long long)w[i - 1] * w1 % mod;
				for (int i = 0; i < n; i += mid << 1)
					for (int j = 0; j < mid; j++) {
						int t = (long long)w[j] * f[i + mid + j] % mod;
						f[i + mid + j] = f[i + j] - t + mod;
						f[i + j] += t;
					}
				if (mid == 1 << 10)
					for (int i = 0; i < n; i++) f[i] %= mod;
			}
			int inv = flag ? 1 : power(n, mod - 2);
			for (int i = 0; i < n; i++) g[i] = f[i] % mod * inv % mod;
			return ;
		}
		poly operator*(poly b) const {
			poly a(*this);
			int n = 1, len = (int)(a.size() + b.size()) - 1;
			while (n < len) n <<= 1;
			a.resize(n), b.resize(n);
			NTT(a, 1), NTT(b, 1);
			poly c(n);
			for (int i = 0; i < n; i++) c[i] = (long long)a[i] * b[i] % mod;
			NTT(c, 0);
			c.resize(len);
			return c;
		}
		poly operator*=(const poly &b) {return *this = *this * b;}
	};
}
using namespace Poly;

int n, x, fac[1000005], inv[1000005];
int H[500005], ans[500005];
poly f, g, cdep, csiz;

int C(int n, int m) {return (long long)fac[n] * inv[m] % mod * inv[n - m] % mod;}
int calc(int x, int p) {
	return (long long)C(2 * x - p - 2, x - p - 1) * (p + 1) % mod * power(x, mod - 2) % mod;
}

int main() {
	freopen("schrodingerstomb.in", "r", stdin);
	freopen("schrodingerstomb.out", "w", stdout);
	scanf("%d%d", &n, &x);
	fac[0] = fac[1] = 1;
	inv[0] = inv[1] = 1;
	for (int i = 2; i <= 2 * n; i++) {
		fac[i] = (long long)fac[i - 1] * i % mod;
		inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
	}
	for (int i = 2; i <= 2 * n; i++) inv[i] = (long long)inv[i - 1] * inv[i] % mod;
	H[0] = 1;
	for (int i = 1; i <= n; i++) H[i] = (C(2 * i, i) - C(2 * i, i - 1) + mod) % mod;
	f.resize(x), g.resize(n - x + 1);
	for (int i = 0; i < x; i++) f[i] = (long long)calc(x, i) * inv[i] % mod;
	for (int i = 0; i < n - x + 1; i++) g[i] = (long long)calc(n - x + 1, i) * inv[i] % mod;
	cdep = f * g;
	cdep.push_back(0);
	for (int i = n; i >= 1; i--) cdep[i] = (long long)cdep[i - 1] * fac[i - 1] % mod;
	for (int i = 0; i < x; i++) f[i] = H[i];
	for (int i = 0; i < n - x + 1; i++) g[i] = H[i];
	csiz = f * g;
	csiz.push_back(0);
	for (int i = n; i >= 1; i--) csiz[i] = (long long)csiz[i - 1] * H[n - i] % mod;
	ans[1] = (long long)H[x - 1] * H[n - x] % mod;
	for (int i = 2; i <= n; i++) ans[i] = ((long long)ans[i - 1] + mod - csiz[n - i + 2] + cdep[i]) % mod;
	for (int i = 1; i <= n; i++) printf("%d\n", ans[i]);
	return 0;
}

4.7

没啥有意思题。

4.8

TopCoder FindPolygons

给你一棵树，找两个不交的连通块使得它们同构，求最大连通块大小。

枚举一条边断开，再枚举其中一个的根，然后设 fu,vf_{u, v} 表示第一棵树里的 uu 和第二棵树里的 vv 为根的最大连通块打小，转移就是两个点的儿子二分图最大权匹配。

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, dp[55][55];
int ans;
struct edge{int u, v;} e[55];
struct graph {
	int tot, hd[55];
	int nxt[105], to[105];
	
	void clear() {tot = 0; memset(hd, 0, sizeof(hd)); return ;}
	void add(int u, int v) {
		nxt[++tot] = hd[u];
		hd[u] = tot;
		to[tot] = v;
		return ;
	}
} g;
struct dsu {
	int fa[55];

	void clear() {for (int i = 1; i < 55; i++) fa[i] = i; return ;}
	int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
	void merge(int x, int y) {fa[find(x)] = find(y); return ;}
	int query(int x, int y) {return find(x) == find(y);}
} d;
struct PrimalDual {
	int n, s, t;
	int f[55], h[55], dis[55], pre[55];
	struct graph {
		int tot, hd[55];
		int nxt[10005], to[10005], flw[10005], cst[10005];

		void clear() {tot = 1; memset(hd, 0, sizeof(hd)); return ;}
		void add(int u, int v, int f, int c) {
			nxt[++tot] = hd[u];
			hd[u] = tot;
			to[tot] = v;
			flw[tot] = f;
			cst[tot] = c;
			return ;
		}
	} g;
	struct node {
		int id, val;

		node() = default;
		node(int _id, int _val): id(_id), val(_val) {}
		bool operator<(const node &x) const {return val > x.val;}
	};

	void clear() {n = s = t = 0; g.clear(); return ;}
	void add_edge(int u, int v, int f, int c) {g.add(u, v, f, c), g.add(v, u, 0, -c); return ;}
	void spfa() {
		queue<int> q;
		memset(f, 0, sizeof(f));
		memset(h, 0x3f, sizeof(h));
		h[s] = 0;
		q.push(s);
		while (!q.empty()) {
			int now = q.front();
			q.pop();
			f[now] = 0;
			for (int i = g.hd[now]; i; i = g.nxt[i])
				if (g.flw[i] && h[g.to[i]] > h[now] + g.cst[i]) {
					h[g.to[i]] = h[now] + g.cst[i];
					if (!f[g.to[i]]) q.push(g.to[i]), f[g.to[i]] = 1;
				}
		}
		return ;
	}
	int dijkstra() {
		priority_queue<node> q;
		memset(dis, 0x3f, sizeof(dis));
		memset(pre, 0, sizeof(pre));
		q.emplace(s, dis[s] = 0);
		while (!q.empty()) {
			int now = q.top().id, tmp = q.top().val;
			q.pop();
			if (dis[now] != tmp) continue;
			for (int i = g.hd[now]; i; i = g.nxt[i])
				if (g.flw[i] && dis[g.to[i]] > dis[now] + g.cst[i] + h[now] - h[g.to[i]]) {
					q.emplace(g.to[i], dis[g.to[i]] = dis[now] + g.cst[i] + h[now] - h[g.to[i]]);
					pre[g.to[i]] = i ^ 1;
				}
		}
		return pre[t];
	}
	pair<int, int> solve() {
		int flow = 0, cost = 0;
		spfa();
		while (dijkstra()) {
			for (int i = 1; i <= n; i++) h[i] += dis[i];
			int mnflow = 0x3f3f3f3f;
			for (int i = t; i != s; i = g.to[pre[i]]) mnflow = min(mnflow, g.flw[pre[i] ^ 1]);
			for (int i = t; i != s; i = g.to[pre[i]]) {
				g.flw[pre[i] ^ 1] -= mnflow;
				g.flw[pre[i]] += mnflow;
			}
			flow += mnflow;
			cost += mnflow * h[t];
		}
		return {flow, cost};
	}
} f;

void dfs2(int now, int fa, int rt, int rtf) {
	for (int i = g.hd[now]; i; i = g.nxt[i])
		if (g.to[i] != fa) dfs2(g.to[i], now, rt, rtf);
	f.clear();
	int s1 = 0, s2 = 0;
	for (int i = g.hd[rt]; i; i = g.nxt[i])
		if (g.to[i] != rtf) s1++;
	for (int i = g.hd[now]; i; i = g.nxt[i])
		if (g.to[i] != fa) s2++;
	f.n = s1 + s2 + 2, f.s = s1 + s2 + 1, f.t = s1 +s2 + 2;
	// eprintf("%d %d %d %d %d %d\n", now, fa, rt, rtf, s1, s2);
	for (int i = g.hd[rt], n1 = 1; i; i = g.nxt[i], n1++) {
		if (g.to[i] == rtf) {n1--; continue;}
		for (int j = g.hd[now], n2 = s1 + 1; j; j = g.nxt[j], n2++) {
			if (g.to[j] == fa) {n2--; continue;}
			f.add_edge(n1, n2, 1, -dp[g.to[i]][g.to[j]]);
		}
	}
	for (int i = 1; i <= s1; i++) f.add_edge(f.s, i, 1, 0);
	for (int i = s1 + 1; i <= s1 + s2; i++) f.add_edge(i, f.t, 1, 0);
	dp[rt][now] = 1 - f.solve().second;
	// eprintf("%d %d %d\n", rt, now, dp[rt][now]);
	ans = max(ans, dp[rt][now]);
	return ;
}
void dfs1(int now, int fa, int rt) {
	// eprintf("%d %d\n", now, fa);
	for (int i = g.hd[now]; i; i = g.nxt[i])
		if (g.to[i] != fa) dfs1(g.to[i], now, rt);
	dfs2(rt, 0, now, fa);
	return ;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &e[i].u), e[i].u++;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &e[i].v), e[i].v++;
	n++;
	for (int i = 1; i < n; i++) {
		g.clear(), d.clear();
		for (int j = 1; j < n; j++)
			if (j != i) g.add(e[j].u, e[j].v), g.add(e[j].v, e[j].u), d.merge(e[j].u, e[j].v);
		// eprintf("%d - %d\n", e[i].u, e[i].v);
		for (int j = 1; j <= n; j++)
			if (d.query(j, e[i].u)) dfs1(j, 0, e[i].v);
	}
	printf("%d\n", ans);
	return 0;
}

TopCoder BitToggler

给一个 01 序列，有一个光标，每次等概率随机一个位置，将光标移动过去并翻转这一位，问变成全 0 或全 1 的期望移动距离。

设 fk,0/1,0/1,0/1f_{k, 0/1, 0/1, 0/1} 表示对于一个点对 (i,j)(i, j)，有 kk 个 11，i,ji, j 为 0/10/1，光标是否在 ii 时的期望移动距离，高斯消元求解即可。

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
// 君の人生は月明かりだ、有りがちだなんて言わせるものか
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, q, pos[1005], idx, id[25][2][2][2];
string s[1005];
double mat[165][165];

int main() {
	scanf("%d", &n);
	for (int i = 1; i < n; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 2; k++)
				for (int f = 0; f < 2; f++)
					if (i >= j + k) id[i][j][k][f] = ++idx;
	for (int i = 1; i < n; i++)
		for (int j = 0; j < 2; j++)
			for (int k = 0; k < 2; k++)
				for (int f = 0; f < 2; f++) {
					if (i < j + k) continue;
					int ID = id[i][j][k][f], num = i - j - k;
					mat[ID][ID] = 1;
					if (i > 0) mat[ID][id[i - 1][j][k][0]] = -(double)num / n;
					if (i < n) mat[ID][id[i + 1][j][k][0]] = -(double)(n - 2 - num) / n;
					mat[ID][id[i + (j ? -1 : 1)][j ^ 1][k][1]] = -1. / n;
					mat[ID][id[i + (k ? -1 : 1)][j][k ^ 1][0]] = -1. / n;
					if (f) mat[ID][idx + 1] = 1. / n;
					// num / n -> (i - 1, j, k, 0)
					// (n - 2 - num) / n -> (i + 1, j, k, 0)
					// 1 / n -> (i + (j ? -1 : 1), j ^ 1, k, 1)
					// 1 / n -> (i + (k ? -1 : 1), j, k ^ 1, 0) + f
				}
	for (int i = 1; i <= idx; i++) {
		double c = mat[i][i];
		for (int j = 1; j <= idx + 1; j++) mat[i][j] /= c;
		for (int j = 1; j <= idx; j++)
			if (j != i && mat[j][i]) {
				double c = mat[j][i];
				// eprintf("%d %lf\n", j, mat[j][i] + mat[i][i] * c);
				for (int k = 1; k <= idx + 1; k++) mat[j][k] -= mat[i][k] * c;
			}
	}
	// eprintf("idx = %d\n", idx);
	// for (int i = 1; i < n; i++)
	// 	for (int j = 0; j < 2; j++)
	// 		for (int k = 0; k < 2; k++)
	// 			for (int f = 0; f < 2; f++)
	// 				if (i >= j + k) eprintf("%d %d %d %d %lf\n", i, j, k, f, mat[id[i][j][k][f]][idx + 1]);
	scanf("%d", &q);
	for (int i = 1; i <= q; i++) cin >> s[i], s[i] = " " + s[i];
	scanf("%d", &q);
	for (int i = 1; i <= q; i++) scanf("%d", &pos[i]), pos[i]++;
	for (int Case = 1; Case <= q; Case++) {
		string s = ::s[Case];
		int pos = ::pos[Case];
		int num = 0;
		for (int i = 1; i <= n; i++) num += s[i] - '0';
		double ans = 0;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= n; j++)
				if (j != i) ans += mat[id[num][s[i] - '0'][s[j] - '0'][i == pos]][idx + 1] * abs(i - j);
		printf("%.12lf ", ans);
	}
	puts("");
	return 0;
}

4.9

TopCoder FindPolygons

求一个整点多边形，使得其周长恰好等于给定的 LL。要求边数最少，在满足边数最少时使最长边与最短边之差最小，输出最长边与最短边的差值。

首先若 LL 是偶数容易构造出矩形使得答案为 11 或 00。然后发现边数大于 44 的时候就会变得很难搞，于是大胆猜测 LL 为奇数时无解。

证明考虑在多边形上走，并记录两维的奇偶性，因为要绕一圈走回原点因此两维的平方的和都是偶数，因此边长也必然是偶数。

然后对于三角形，预处理出所有勾股数之后暴力即可。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <tuple>
#include <cmath>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int L, ans = 1e9;
vector<pair<int, int>> vec[5005];

int main() {
	scanf("%d", &L);
	if (L == 2) {puts("-1"); return 0;}
	for (int i = 0; i <= L; i++)
		for (int j = i; j <= L; j++) {
			int v = i * i + j * j;
			int kk = 0;
			for (int k = max<int>(sqrt(v) - 5, 0); k * k <= v; k++)
				if (k * k == v) {kk = k; break;}
			if (kk && kk <= L) vec[kk].emplace_back(i, j);
		}
	// for (auto i : vec[4]) eprintf("%d %d\n", i.first, i.second);
	for (int i = 1; i <= L - 2; i++)
		for (auto p : vec[i])
			for (int j = i; j < L - i; j++)
				for (auto q : vec[j]) {
					int k = L - i - j;
					int a = abs(p.first - q.first), b = abs(p.second - q.second);
					if (p.second * q.first != q.second * p.first && k * k == a * a + b * b)
						ans = min(ans, max({abs(k - i), abs(k - j), abs(i - j)}));
					a = abs(p.first - q.second), b = abs(p.second - q.first);
					if (p.second * q.second != q.first * p.first && k * k == a * a + b * b)
						ans = min(ans, max({abs(k - i), abs(k - j), abs(i - j)}));
				}
	if (ans < 1e9) {printf("%d\n", ans); return 0;}
	if (L % 2 == 0) {printf("%d\n", L % 4 == 0 ? 0 : 1); return 0;}
	puts("-1");
	return 0;
}

4.12

C

神题！

等概率随机一个 nn 个点有标号有根树，每条边权值在 [0,m]∩N[0, m] \cap \mathbb{N} 中等概率随机，然后在根上放一颗棋子，两个人轮流移动，要求一条边经过次数不能超过它的边权，无法移动者输，问先手必胜的概率。

首先显然可以把边权对 22 取模，然后设 p0p_0 为边权为 00 的概率。

朴素做法是考虑设 fif_i 为所有 ii 个点的树先手必败的概率之和，然后设 gig_i 为所有 ii 个点的树，钦定根的编号为 11 时先手必败的概率之和。

用 F(x)F(x) 和 G(x)G(x) 表示 f,gf, g 的 EGF，可以推出：

H(x)=∑i≥1ii−1xi!G(x)=exp⁡(H(x)−xG(x)+p0xG(x))H(x) = \sum\limits_{i\ge 1} \frac{i^{i - 1} x}{i!} \\ G(x) = \exp(H(x) - xG(x) + p_0xG(x))

并且 F(x)=xG(x)F(x) = xG(x)，因此：

F(x)=xexp⁡(H(x)−F(x)+p0F(x))F(x) = x\exp(H(x) - F(x) + p_0F(x))

然后答案就是 [xnn!](H(x)−F(x))nn−1\frac{[\frac{x^n}{n!}](H(x) - F(x))}{n^{n - 1}}。

朴素做法是直接牛顿迭代，但是爆爆爆。

首先有性质 H(x)=xeH(x)H(x) = xe^{H(x)}。

大力化简：

F(x)=xexp⁡(H(x)−F(x)+p0F(x))F(x)=H(x)exp⁡((p0−1)F(x))\begin{aligned} F(x) &= x\exp(H(x) - F(x) + p_0F(x)) \\ F(x) &= H(x) \exp((p_0 - 1)F(x)) \end{aligned}

令 p=p0−1p = p_0 - 1。设 H−1(x)H^{-1}(x) 为 H(x)H(x) 的复合逆（H−1(H(x))=H(H−1(x))H^{-1}(H(x)) = H(H^{-1}(x))），则：

F(x)=H(x)epF(x)H−1(pF(x))⋅F(x)=H−1(pF(x))⋅epF(x)⋅H(x)\begin{aligned} F(x) &= H(x) e^{pF(x)} \\ H^{-1}(pF(x)) \cdot F(x) &= H^{-1}(pF(x)) \cdot e^{pF(x)} \cdot H(x) \\ \end{aligned}

把 pF(x)pF(x) 视为 H(y)H(y)，就有 H−1(H(y))⋅eH(y)=yeH(y)=H(y)=pF(x)H^{-1}(H(y)) \cdot e^{H(y)} = ye^{H(y)} = H(y) = pF(x)，因此：

H−1(pF(x))⋅F(x)=pF(x)⋅H(x)H−1(pF(x))=pH(x)F(x)=H(pH(x))p\begin{aligned} H^{-1}(pF(x)) \cdot F(x) &= pF(x) \cdot H(x) \\ H^{-1}(pF(x)) &= pH(x) \\ F(x) &= \frac{H(pH(x))}{p} \end{aligned}

然后我们要求 [xn]F(x)[x^n]F(x)，也就是：

[xn]F(x)=[xn]H(pH(x))p=[xn]1p∑i≥1ii−1i!(pH(x))i=∑i≥1(ip)i−1i![xn]H(x)i\begin{aligned} [x^n]F(x) &= [x^n]\frac{H(pH(x))}{p} \\ &= [x^n]\frac{1}{p} \sum\limits_{i\ge 1} \frac{i^{i - 1}}{i!} (pH(x))^i \\ &= \sum\limits_{i\ge 1} \frac{(ip)^{i - 1}}{i!} [x^n]H(x)^i \end{aligned}

考虑 [xn]H(x)i[x^n]H(x)^i 的组合意义，就是 nn 个点组成 ii 个有根树的方案数乘上 i!n!\frac{i!}{n!}。其中 i!i! 是因为有根树无序。

然后这个东西根据广义凯莱公式可以得到答案为 i(ni)nn−i−1i\binom{n}{i}n^{n - i - 1}。因此：

∑i≥1(ip)i−1i![xn]H(x)i=∑i≥1(ip)i−1n!i(ni)nn−i−1\sum\limits_{i\ge 1} \frac{(ip)^{i - 1}}{i!} [x^n]H(x)^i = \sum\limits_{i\ge 1} \frac{(ip)^{i - 1}}{n!} i\binom{n}{i}n^{n - i - 1}

然后就做完了。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, p, mod, fac[1000005], inv[1000005], ans;

int power(int a, int b) {
	// eprintf("%d %d\n", a, b);
	int ans = 1;
	while (b) { 
		if (b & 1) ans = (long long)ans * a % mod;
		a = (long long)a * a % mod;
		b >>= 1;
	}
	return ans % mod;
}
int C(int n, int m) {return (long long)fac[n] * inv[m] % mod * inv[n - m] % mod;}

int main() {
	freopen("win.in", "r", stdin);
	freopen("win.out", "w", stdout);
	scanf("%d%d%d", &n, &p, &mod);
	p = (long long)(p + 1) / 2 * power(p + 1, mod - 2) % mod;
	p = (mod - p) % mod;
	fac[0] = fac[1] = 1;
	inv[0] = inv[1] = 1;
	for (int i = 2; i <= n; i++) {
		fac[i] = (long long)fac[i - 1] * i % mod;
		inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
	}
	inv[0] = inv[1] = 1;
	for (int i = 2; i <= n; i++) inv[i] = (long long)inv[i - 1] * inv[i] % mod;
	for (int i = 1; i <= n; i++) {
		int c = i < n ? power(n, n - i - 1) : power(n, mod - 2);
		ans = (ans +
			(long long)power((long long)i * p % mod, i - 1) * inv[n] % mod *
			i % mod * C(n, i) % mod * c) % mod;
	}
	// eputs("?");
	ans = (long long)ans * fac[n] % mod;
	ans = (power(n, n - 1) - ans + mod) % mod;
	ans = (long long)ans * power(power(n, n - 1), mod - 2) % mod;
	printf("%d\n", ans);
	return 0;
}

4.13

都。是。屎。

4.15

TopCoder MagicMolecule

给一张无向图，点有点权，找一个大小大于等于 2n3\frac{2n}{3} 的团使得点权和最大。

怎么每次看到这个套路都不会做……

维护一个集合 SS，初始时是全集，每次扣出两个没有边的点从集合中删掉，最后 SS 一定是一个团。并且如果存在大于等于 2n3\frac{2n}{3} 的团则 ∣S∣≥n3|S| \ge \frac{n}{3}，因此扣出来的点对也只有 n3\frac{n}{3}，暴力枚举每个点对选哪个或不选，时间复杂度为 O(n3n3)O(n3^\frac{n}{3})。

题解说不用枚举不选的情况，不知道为啥。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, a[55], m, u[55], v[55], ans = -1;
long long S, g[55];

void dfs(int now, long long T, long long S, int sum) {
	if (now == m + 1) {
		if (3 * __builtin_popcountll(S | T) < 2 * n) return ;
		for (long long SS = S; SS; SS -= SS & -SS) sum += a[__builtin_ctzll(SS)];
		ans = max(ans, sum);
		return ;
	}
	dfs(now + 1, T, S, sum);
	if ((T & g[u[now]]) == T) dfs(now + 1, T | 1ll << u[now], S & g[u[now]], sum + a[u[now]]);
	if ((T & g[v[now]]) == T) dfs(now + 1, T | 1ll << v[now], S & g[v[now]], sum + a[v[now]]);
	return ;
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 0; i < n; i++) cin >> a[i];
	cin >> n;
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			char c;
			cin >> c;
			if (c == 'Y') g[i] |= 1ll << j;
		}
	S = (1ll << n) - 1;
	for (int i = 0; i < n; i++)
		if (S >> i & 1)
			for (int j = 0; j < n; j++)
				if (j != i && S >> j & 1 && !(g[i] >> j & 1)) {
					// eprintf("%d %d\n", i, j);
					S ^= 1ll << i | 1ll << j;
					m++;
					u[m] = i, v[m] = j;
					break;
				}
	if (3 * (n - m) < 2 * n) {cout << "-1\n"; return 0;}
	dfs(1, 0, S, 0);
	cout << ans << '\n';
	return 0;
}

4.16

TopCoder LittleElephantAndPermutationDiv1

对于两个长度为 nn 的排列 A,BA, B，定义其权值为 ∑i=1nmax⁡(Ai,Bi)\sum_{i = 1}^n \max(A_i, B_i)，问有多少对排列使得其权值大于等于 KK。

首先显然可以钦定 Ai=iA_i = i，最后 ×n!\times n! 即可。

然后考虑从大到小填数，但是如果填到较小的地方就会产生后效性，不妨使每个位置都在较小值确定时确定，也就是对于一个 (i,Bi)(i, B_i)，我们在考虑到 min⁡(i,Bi)\min(i, B_i) 时才确定 BiB_i 的取值。

那么我们就要记录当前枚举到的值 ii，没有确定位置的数的个数 jj，以及当前权值 kk。

转移就考虑 ii 填到什么位置：

  • 填到 ii：dpi,j,k+i←dpi,j,k+i+dpi+1,j,kdp_{i, j, k + i} \gets dp_{i, j, k + i} + dp_{i + 1, j, k}。
  • 填到 <i< i，ii 这一位填 >i> i 的数，则枚举 ii 这位填哪一个：dpi,j,k+i←dpi+1,j,k⋅jdp_{i, j, k + i} \gets dp_{i + 1, j, k} \cdot j。
  • 填到 <i< i，ii 这一位填 <i< i 的数：dpi,j,k+2i←dpi,j,k+2i+dpi+1,j,kdp_{i, j, k + 2i} \gets dp_{i, j, k + 2i} + dp_{i + 1, j, k}。
  • 填到 >i> i，这一位填 >i> i 的数，则枚举填到哪以及这一位填哪个：dpi,j−1,k←dpi,j−1,k+dpi+1,j,k⋅j2dp_{i, j - 1, k} \gets dp_{i, j - 1, k} + dp_{i + 1, j, k} \cdot j^2。
  • 填到 >i> i，这一位填 <i< i的数，则枚举填到哪：dpi,j,k+i←dpi,j,k+i+dpi+1,j,k⋅jdp_{i, j, k + i} \gets dp_{i, j, k + i} + dp_{i + 1, j, k} \cdot j。

然后就做完了。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 1e9 + 7;

int n, m, dp[55][55][2555];

int main() {
	scanf("%d%d", &n, &m);
	dp[n + 1][0][0] = 1;
	for (int i = n; i >= 1; i--)
		for (int j = 0; j <= min(i, n - i); j++)
			for (int k = 0; k <= (i + 1 + n) * (n - i); k++) {
				dp[i][j][k + i] = (dp[i][j][k + i] + dp[i + 1][j][k]) % mod;
				dp[i][j][k + i] = (dp[i][j][k + i] + (long long)dp[i + 1][j][k] * j) % mod;
				dp[i][j + 1][k + 2 * i] = (dp[i][j + 1][k + 2 * i] + (long long)dp[i + 1][j][k]) % mod;
				if (j) {
					dp[i][j - 1][k] = (dp[i][j - 1][k] + (long long)dp[i + 1][j][k] * j % mod * j) % mod;
					dp[i][j][k + i] = (dp[i][j][k + i] + (long long)dp[i + 1][j][k] * j) % mod;
				}
			}
	// eprintf("%d\n", dp[2][1][4]);
	int ans = 0;
	for (int i = m; i <= (1 + n) * n; i++) ans = (ans + dp[1][0][i]) % mod;
	for (int i = 1; i <= n; i++) ans = (long long)ans * i % mod;
	printf("%d\n", ans);
	return 0;
}

4.19

B

屎。记录这题的原因是它差点破了我赛时写的最长的码的记录。当前记录保持者是过河卒，6629B。这题是 6359B。不过过河卒当时没过（

给定 nn 个矩形，定义 E(i,j)E(i, j) 当且仅当矩形 ii 和矩形 jj 相交时值为 11，否则值为 00，求满足 Ei,j+Ei,k+Ej,k=0E_{i, j} + E_{i, k} + E_{j, k} = 0 的 (i,j,k)(i, j, k) 的数量。

显然钦定其中某几个为 11 然后容斥。

钦定 00 个为 11 的情况：答案为 n(n−1)(n−2)6\frac{n(n - 1)(n - 2)}{6}。

钦定 11 个为 11 的情况：枚举相交的两个矩形，然后剩下的一个随便选，因此答案为相交的矩形对的个数乘上 n−2n - 2。

考虑相交矩形对数怎么做，我们按 xx 坐标扫描线，在遇到时把 yy 坐标的区间加入，离开时删除，然后在离开时统计与之相交的区间个数，这个可以维护以每个点为左 / 右端点的区间个数，然后总个数减去右端点小于当前区间左端点的和左端点大于当前区间右端点的即可。

钦定 22 个为 11 的情况：也就是其中一个矩形与另外两个都有交，我们要对每个矩形数与之相交的矩形个数。

用 (l,r,d,u)(l, r, d, u) 表示 xx 坐标在 [l,r][l, r]，yy 坐标在 [d,u][d, u] 的矩形，那么差分一下，求与 (1,r,d,u)(1, r, d, u) 交的个数再减去只与 (1,l−1,d,u)(1, l - 1, d, u) 交的个数即可。

前者在扫描线时只加入不删除，后者在扫描线时在离开时删除即可。

钦定 33 个为 11 的情况：也就是三个矩形有交。

依然扫描线，在离开一个矩形时统计，也就是对于一个区间 (d,u)(d, u)，求与之有交的有交区间对的个数。

先容斥成所有与之有交的区间对减去与之有交的不交区间对。

然后再把与之有交的不交区间对容斥成所有不交区间对减去钦定其中一个无交的区间对加上两个都无交的区间对。

这个东西用线段树维护两个序列 a,ba, b，在加入区间 [l,r][l, r] 时，ar←ar+1,∀i∈[1,l−1],bi←bi+1a_r \gets a_r + 1, \forall i \in [1, l - 1], b_i \gets b_i + 1，删除区间时减 11，这样上面要求的都转化成了询问一个区间 [l,r][l, r] 的 ∑i=lraibi\sum\limits_{i = l}^r a_i b_i，这个可以用线段树维护。然后对于左端点同样维护一个线段树即可。

时间复杂度 O(nlog⁡n)O(n\log n)。

代码里 dd 和 uu 反了一下。

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, dataType, M, m, b[400005], sum, num[200005];
long long ans;
struct rect {int l, r, d, u;} a[200005];
struct BIT {
	int w[400005];

	void update(int pos, int val) {
		for (; pos < 400005; pos += pos & -pos) w[pos] += val;
		return ;
	}
	int query(int pos) {
		int res = 0;
		for (; pos >= 1; pos -= pos & -pos) res += w[pos];
		return res;
	}
} trL, trR;
vector<pair<int, int>> vec[400005];
struct SegmenTree {
#define ls(x) (x * 2)
#define rs(x) (x * 2 + 1)

	long long ans[1600005], sumb[1600005];
	int suma[1600005], lzy[1600005];
	int l[1600005], r[1600005];

	void build(int ll, int rr, int now = 1) {
		l[now] = ll, r[now] = rr;
		if (ll == rr) return ;
		int mid = (ll + rr) / 2;
		build(ll, mid, ls(now)), build(mid + 1, rr, rs(now));
		return ;
	}
	void down(int now) {
		ans[ls(now)] += (long long)lzy[now] * suma[ls(now)];
		ans[rs(now)] += (long long)lzy[now] * suma[rs(now)];
		sumb[ls(now)] += (long long)lzy[now] * (r[ls(now)] - l[ls(now)] + 1);
		sumb[rs(now)] += (long long)lzy[now] * (r[rs(now)] - l[rs(now)] + 1);
		lzy[ls(now)] += lzy[now], lzy[rs(now)] += lzy[now];
		lzy[now] = 0;
		return ;
	}
	void update1(int ll, int rr, int val, int now = 1) {
		// if (now == 1) eprintf("upd: %d %d %d\n", ll, rr, val);
		if (ll <= l[now] && r[now] <= rr) {
			ans[now] += (long long)val * suma[now];
			sumb[now] += (long long)val * (r[now] - l[now] + 1);
			lzy[now] += val;
			return ;
		}
		if (lzy[now]) down(now);
		int mid = (l[now] + r[now]) / 2;
		if (ll <= mid) update1(ll, rr, val, ls(now));
		if (mid < rr) update1(ll, rr, val, rs(now));
		ans[now] = ans[ls(now)] + ans[rs(now)];
		suma[now] = suma[ls(now)] + suma[rs(now)];
		sumb[now] = sumb[ls(now)] + sumb[rs(now)];
		return ;
	}
	void update2(int pos, int val, int now = 1) {
		// if (now == 1) eprintf("upd: %d %d\n", pos, val);
		if (l[now] == r[now]) {suma[now] += val; ans[now] += sumb[now] * val; return ;}
		if (lzy[now]) down(now);
		int mid = (l[now] + r[now]) / 2;
		if (pos <= mid) update2(pos, val, ls(now));
		else update2(pos, val, rs(now));
		ans[now] = ans[ls(now)] + ans[rs(now)];
		suma[now] = suma[ls(now)] + suma[rs(now)];
		sumb[now] = sumb[ls(now)] + sumb[rs(now)];
		return ;
	}
	long long query(int ll, int rr, int now = 1) {
		if (ll <= l[now] && r[now] <= rr) return ans[now];
		if (lzy[now]) down(now);
		int mid = (l[now] + r[now]) / 2;
		long long res = 0;
		if (ll <= mid) res += query(ll, rr, ls(now));
		if (mid < rr) res += query(ll, rr, rs(now));
		return res;
	}

#undef ls
#undef rs
} Ltr, Rtr;

void clear() {
	sum = 0;
	memset(trL.w, 0, sizeof(trL.w));
	memset(trR.w, 0, sizeof(trR.w));
	return ;
}
void update(int l, int r, int v) {
	// if (v == 1) eprintf("add: %d %d\n", l, r);
	// else eprintf("del: %d %d\n", l, r);
	sum += v;
	trL.update(l, v), trR.update(r, v);
	return ;
}
int query(int l, int r) {
	return trR.query(l - 1) + trL.query(M) - trL.query(r);
}

int main() {
	freopen("rect.in", "r", stdin);
	freopen("rect.out", "w", stdout);
	scanf("%d%d", &n, &dataType);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d%d%d", &a[i].l, &a[i].r, &a[i].u, &a[i].d);
		// eprintf("[%d, %d]\n", a[i].u, a[i].d);
		b[++m] = a[i].u, b[++m] = a[i].d;
	}
	sort(b + 1, b + m + 1);
	m = unique(b + 1, b + m + 1) - b - 1;
	for (int i = 1; i <= n; i++) {
		a[i].u = lower_bound(b + 1, b + m + 1, a[i].u) - b;
		a[i].d = lower_bound(b + 1, b + m + 1, a[i].d) - b;
	}
	M = m, m = 0;
	for (int i = 1; i <= n; i++) b[++m] = a[i].l, b[++m] = a[i].r;
	sort(b + 1, b + m + 1);
	m = unique(b + 1, b + m + 1) - b - 1;
	for (int i = 1; i <= n; i++) {
		a[i].l = lower_bound(b + 1, b + m + 1, a[i].l) - b;
		a[i].r = lower_bound(b + 1, b + m + 1, a[i].r) - b;
	}
	// for (int i = 1; i <= n; i++) eprintf("%d %d %d %d\n", a[i].l, a[i].r, a[i].u, a[i].d);
	ans = (long long)n * (n - 1) * (n - 2) / 6;
	for (int i = 1; i <= n; i++) vec[a[i].l].emplace_back(0, i), vec[a[i].r].emplace_back(1, i);
	for (int i = 1; i <= m; i++) {
		sort(vec[i].begin(), vec[i].end());
		for (auto j : vec[i])
			if (j.first == 0) update(a[j.second].u, a[j.second].d, 1);
			else {
				update(a[j.second].u, a[j.second].d, -1);
				ans -= (long long)(sum - query(a[j.second].u, a[j.second].d)) * (n - 2);
			}
	}
	// eprintf("%lld\n", ans);
	clear();
	for (int i = 1; i <= m; i++) {
		for (auto j : vec[i])
			if (j.first == 0) update(a[j.second].u, a[j.second].d, 1);
			else num[j.second] += sum - query(a[j.second].u, a[j.second].d) - 1;
	}
	clear();
	for (int i = 1; i <= m; i++) {
		for (auto j : vec[i])
			if (j.first == 0) num[j.second] -= sum - query(a[j.second].u, a[j.second].d);
			else update(a[j.second].u, a[j.second].d, 1);
	}
	// for (int i = 1; i <= n; i++) eprintf("%d ", num[i]);
	// eputs("");
	for (int i = 1; i <= n; i++) ans += (long long)num[i] * (num[i] - 1) / 2;
	// eprintf("%lld\n", ans);
	// eputs("---------");
	clear();
	Ltr.build(1, M), Rtr.build(1, M);
	for (int i = 1; i <= m; i++) {
		for (auto j : vec[i])
			if (j.first == 0) {
				update(a[j.second].u, a[j.second].d, 1);
				if (a[j.second].u > 1) Rtr.update1(1, a[j.second].u - 1, 1);
				Rtr.update2(a[j.second].d, 1);
				if (a[j.second].d < M) Ltr.update1(a[j.second].d + 1, M, 1);
				Ltr.update2(a[j.second].u, 1);
			} else {
				// eprintf("Solving %d:\n", j.second);
				update(a[j.second].u, a[j.second].d, -1);
				if (a[j.second].u > 1) Rtr.update1(1, a[j.second].u - 1, -1);
				Rtr.update2(a[j.second].d, -1);
				if (a[j.second].d < M) Ltr.update1(a[j.second].d + 1, M, -1);
				Ltr.update2(a[j.second].u, -1);
				int num = sum - query(a[j.second].u, a[j.second].d);
				// eprintf("%d\n", num);
				long long res = Rtr.query(1, M);
				if (a[j.second].u > 1) res -= Rtr.query(1, a[j.second].u - 1);
				// eprintf("%lld\n", res);
				if (a[j.second].d < M) res -= Ltr.query(a[j.second].d + 1, M);
				res += (long long)trR.query(a[j.second].u - 1) *
					(trL.query(M) - trL.query(a[j.second].d));
				res = (long long)num * (num - 1) / 2 - res;
				// eprintf("%d %lld\n", j.second, res);
				ans -= res;
			}
	}
	printf("%lld\n", ans);
	return 0;
}

C

有一棵树，定义 dis(u,v)dis(u, v) 为 uu 到 vv 路径上所有点编号的异或和，每次可以询问一个点 uu 和点集 SS，交互库会回答 xorv∈Sdis(u,v)\mathbin{\mathrm{xor}}_{v\in S} dis(u, v)，要求在 4000040000 次询问内求出这课树，n≤3000n\le 3000。

钦定 11 为根。先用 n−1n - 1 次询问求出每个点到 11 的答案，记为 valival_i，则有：LCA(u,v)=valuxorvalvxordis(u,v)LCA(u, v) = val_u \mathbin{\mathrm{xor}} val_v \mathbin{\mathrm{xor}} dis(u, v)。

然后就有了一个 n2n^2 的做法。

正解是考虑维护已知点的虚树。假设当前在 rr 的子树内，要插入 uu。

假设 rr 有偶数个儿子，我们询问 uu 和 rr 的儿子集合，设得到的值是 VV：

  • 若 V=0V = 0，说明 uu 是 rr 的儿子。
  • 若 VxorrV \mathbin{\mathrm{xor}} r 是 rr 的一个儿子，则 uu 在这个儿子的子树内，递归处理。
  • 若 Vxorr=uV \mathbin{\mathrm{xor}} r = u，说明 uu 在 rr 和某个儿子的边上，我们可以二分询问一个儿子的前缀找到那个儿子。
  • 否则就是 uu 和某个儿子的 LCA 为 VxorrV \mathbin{\mathrm{xor}} r，同样的二分找到那个儿子即可。

但是这样每次往下走一层，复杂度显然不对，而且无法处理儿子数是奇数的情况。

考虑对虚树重剖，先 check 是否在重儿子内，如果不在则可以通过添加或删除重儿子使得儿子数是偶数。

然后是在重儿子上的情况，我们在 check 时询问重链的链底，这样就可以知道 uu 在重链上哪个点的子树内。

如果这个点已经在虚树上了，就直接进入子树递归就好了。否则二分找出他在虚树上的父亲，然后把这个点和 uu 插进去。

复杂度分析与重链剖分类似，是 nlog⁡nn\log n 的。

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
105
106
107
108
109
110
// 長い夜の終わりを信じながら
// Think twice, code once.
#include "hypercube.h"
#include <cstdio>
#include <string>
#include <cassert>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n;
int val[3005], siz[3005], son[3005], mp[3005][3005], vis[3005];
vector<int> g[3005];

int getLCA(int u, int v) {
	return !mp[u][v] ? mp[u][v] = mp[v][u] = val[u] ^ val[v] ^ query(u, {v}) : mp[u][v];
}
void dfs(int now) {
	siz[now] = 1, son[now] = 0;
	for (int v : g[now]) {
		dfs(v);
		siz[now] += siz[v];
		if (siz[v] > siz[son[now]]) son[now] = v;
	}
	return ;
}
void erase(int u, int v) {
	for (int i = 0; i < (int)g[u].size(); i++)
		if (g[u][i] == v) g[u].erase(g[u].begin() + i);
	return ;
}
int Query(int u, vector<int> &S) {
	int ans = 0;
	for (int i : S) ans ^= val[u] ^ val[i];
	ans ^= query(u, S);
	return ans;
}
void insert(int u, int now) {
	// assert(vis[now]);
	// eprintf("insert(%d, %d);\n", u, now);
	if (g[now].empty()) {g[now].push_back(u); return ;}
	vector<int> vec;
	vec.push_back(now);
	while (son[vec.back()]) vec.push_back(son[vec.back()]);
	int tmp = getLCA(vec.back(), u);
	if (tmp != now) {
		for (int i : vec)
			if (tmp == i) {insert(u, tmp); return ;}
		int l = 0, r = vec.size() - 1;
		while (l < r) {
			int mid = (l + r) / 2 + 1;
			if (getLCA(vec[mid], u) == vec[mid]) l = mid;
			else r = mid - 1;
		}
		erase(vec[l], vec[l + 1]);
		g[vec[l]].push_back(tmp);
		g[tmp].push_back(vec[l + 1]);
		if (tmp != u) g[tmp].push_back(u);
		vis[tmp] = 1;
		return ;
	}
	vector<int>().swap(vec);
	for (int v : g[now])
		if (v != son[now]) vec.push_back(v);
	if (vec.size() % 2) vec.push_back(son[now]);
	// eprintf("%d\n", (int)vec.size());
	if (vec.empty()) {g[now].push_back(u); return ;}
	tmp = Query(u, vec);
	if (!tmp) {g[now].push_back(u); return ;}
	if (!vis[tmp ^ now]) {
		int l = 0, r = vec.size() - 1;
		while (l < r) {
			int mid = (l + r) / 2;
			vector<int> qvec(vec.begin(), vec.begin() + mid + 1);
			int tmp = Query(u, qvec);
			if (tmp != 0 && tmp != now) r = mid;
			else l = mid + 1;
		}
		erase(now, vec[r]);
		tmp ^= now;
		g[now].push_back(tmp);
		g[tmp].push_back(vec[r]);
		if (tmp != u) g[tmp].push_back(u);
		vis[tmp] = 1;
		return ;
	}
	insert(u, tmp ^ now);
	return ;
}

void solve(int n, int Q, int dataType) {
	::n = n;
	val[1] = 1;
	for (int i = 2; i <= n; i++) val[i] = query(1, {i});
	for (int i = 1; i <= n; i++) vector<int>().swap(g[i]);
	memset(mp, 0, sizeof(mp));
	memset(siz, 0, sizeof(siz));
	memset(son, 0, sizeof(son));
	memset(vis, 0, sizeof(vis));
	vis[1] = 1;
	for (int i = 2; i <= n; i++)
		if (!vis[i]) insert(i, 1), vis[i] = 1, dfs(1);
	for (int i = 1; i <= n; i++)
		for (int j : g[i]) report(i, j);
	return ;
}

4.20

TopCoder HungryCowsMedium

数轴原点有 nn 头牛，还有 mm 个谷仓，每一时刻每头牛可以往左移动一单位距离或往右移动一单位距离或原地不懂，当与某一谷仓在同一位置时也可以吃一单位食物，同一时刻一个谷仓至多有一头牛在吃食物。第 ii 头牛要吃 aia_i 单位食物，问需要的最小时间。

胡乱分析。

显然可以二分答案，设答案为 TT，则第 ii 头牛最多移动 T−aiT - a_i 单位距离，因此其只能吃到位置在 [0,T−ai][0, T - a_i] 的谷仓。

考虑将仓库按位置从小到大排序，牛按 aia_i 从大到小排序。
容易想到牛不会往回走，因此只要能够把每头牛在能吃到的谷仓里面吃饱，不需要考虑路上的时间。

至于等待的时间，我们让要跑两个谷仓的牛在第一个谷仓第一个吃，在第二个谷仓最后一个吃即可，显然这样处理也不需要考虑等待的时间。

然后就做完了。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, cow[305], m, barn[305];

int check(long long limit) {
	long long t = 0;
	int j = 1;
	for (int i = 1; i <= m && j <= n; i++) {
		if (barn[i] + cow[j] > limit) return 0;
		t += limit - barn[i] - cow[j];
		j++;
		while (j <= n && cow[j] <= t) t -= cow[j++];
	}
	return j > n;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &cow[i]);
	sort(cow + 1, cow + n + 1, greater<>());
	scanf("%d", &m);
	for (int i = 1; i <= m; i++) scanf("%d", &barn[i]);
	sort(barn + 1, barn + m + 1);
	long long l = 0, r = 4e11;
	while (l < r) {
		long long mid = (l + r) / 2;
		if (check(mid)) r = mid;
		else l = mid + 1;
	}
	printf("%lld\n", r);
	return 0;
}

TopCoder FoxConnection

有一棵 nn 个点的树，其中某些点上有狐狸，每次可以让一只狐狸移动到相邻的节点，要求最终每个点至多有一只狐狸且有狐狸的点形成一个连通块，求最小移动距离之和。

设 dpi,jdp_{i, j} 表示 ii 子树中有 jj 只狐狸，且 ii 上有狐狸的答案，枚举儿子，然后枚举儿子子树内的狐狸数，算出这条边被经过的次数然后转移即可。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, m, a[55], siz[55];
int ans = 0x3f3f3f3f, dp[55][55], tmp[55];
struct edge {int x, y;} e[55];
struct graph {
	int tot, hd[55];
	int nxt[105], to[105];

	void add(int u, int v) {
		nxt[++tot] = hd[u];
		hd[u] = tot;
		to[tot] = v;
		return ;
	}
} g;

void dfs(int now, int fa) {
	siz[now] = a[now];
	memset(dp[now], 0, sizeof(dp[now]));
	for (int i = g.hd[now]; i; i = g.nxt[i])
		if (g.to[i] != fa) {
			dfs(g.to[i], now);
			memset(tmp, 0x3f, sizeof(tmp));
			for (int j = 0; j <= m; j++)
				for (int k = 0; k <= m - j; k++)
					tmp[j + k] = min(tmp[j + k], dp[now][j] + dp[g.to[i]][k] + abs(siz[g.to[i]] - k));
			memcpy(dp[now], tmp, sizeof(dp[now]));
			siz[now] += siz[g.to[i]];
		}
	for (int i = m; i >= 1; i--) dp[now][i] = dp[now][i - 1];
	return ;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &e[i].x);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &e[i].y);
	n++;
	for (int i = 1; i < n; i++) g.add(e[i].x, e[i].y), g.add(e[i].y, e[i].x);
	for (int i = 1; i <= n; i++) {
		char c;
		cin >> c;
		m += (a[i] = c == 'Y');
	}
	for (int i = 1; i <= n; i++) {
		dfs(i, 0);
		// eprintf("%d %d\n", i, dp[3][1]);
		// for (int j = 1; j <= n; j++) eprintf("%d ", dep[j]);
		// eputs("");
		ans = min(ans, dp[i][m]);
	}
	printf("%d\n", ans);
	return 0;
}

TopCoder FoxSearchingRuins

W×HW \times H 的网格上有 nn 个宝石，第 ii 个宝石在第 xix_i 列 yiy_i 行，价值 viv_i，初始时从第 00 行任意列出发，给出左右移动的次数限制和左右移动一单位需要的时间，向下移动一单位需要的时间，问获得的宝石的价值之和达到目标需要的最小的时间。

设 dpi,jdp_{i, j} 表示在宝石 ii 的位置，左右移动了 jj 次的最大价值，显然时间就是 jj 乘左右移动时间加 ii 的深度乘向下移动的时间。

先考虑同一层，发现访问的是一段区间并且一定是走到某个端点然后走完整个区间，那设状态 0/1/20/1/2 表示在往端点走 / 从右端点往左走 / 从左端点往右走，在状态为 00 时不拿宝石即可。

然后考虑跨层的转移，发现从 uu 走到 vv，需要的左右移动次数为 ∣xu−xv∣|x_u - x_v|，绝对值拆开，设原本的次数为 jj，新次数为 j′j'，则有 j′=j+xu−xv(xu>xv)j' = j + x_u - x_v (x_u > x_v) 或 j′=j−xu+xv(xu<xv)j' = j - x_u + x_v (x_u < x_v)，也就是 j′+xv=j+xu(xu>xv)j' + x_v = j + x_u (x_u > x_v) 或 j′−xv=j−xu(xu<xv)j' - x_v = j - x_u (x_u < x_v)，那么用两个数组维护，需要支持单点修改和查询前缀或后缀最大值，用树状数组维护即可。

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
105
106
107
108
109
110
111
112
113
114
115
116
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <map>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int h, w, n, m, goal, lrcost, dcost, seed[10];
struct node {int x, y, v;} a[1005];
int _, ry[1005];
vector<int> vec[1005];
int dp[1005][1005][3];
long long ans = 0x3f3f3f3f3f3f3f3f;
map<pair<int, int>, int> mp;
struct BIT {
	int w[1005];
	
	void update(int pos, int val) {
		for (; pos < 1005; pos += pos & -pos) w[pos] = max(w[pos], val);
		return ;
	}
	int query(int pos) {
		int res = 0;
		for (; pos >= 1; pos -= pos & -pos) res = max(res, w[pos]);
		return res;
	}
} mx[2][3005];

int main() {
	scanf("%d%d%d%d", &w, &h, &n, &m);
	scanf("%d%d%d", &goal, &lrcost, &dcost);
	scanf("%d", &seed[0]);
	for (int i = 0; i < 10; i++) scanf("%d", &seed[i]);
	a[1].x = ((long long)seed[1] * seed[0] + seed[2]) % w;
	a[1].y = ((long long)seed[4] * seed[3] + seed[5]) % h;
	a[1].v = ((long long)seed[7] * seed[6] + seed[8]) % seed[9];
	mp[{a[1].x, a[1].y}] = 1;
	for (int i = 2; i <= n; i++) {
		a[i].x = ((long long)seed[1] * a[i - 1].x + seed[2]) % w;
		a[i].y = ((long long)seed[4] * a[i - 1].y + seed[5]) % h;
		a[i].v = ((long long)seed[7] * a[i - 1].v + seed[8]) % seed[9];
		if (mp.count({a[i].x, a[i].y})) a[mp[{a[i].x, a[i].y}]].v += a[i].v;
		else mp[{a[i].x, a[i].y}] = i;
	}

	for (int i = 1; i <= n; i++) ry[i] = a[i].y;
	sort(ry + 1, ry + n + 1);
	_ = unique(ry + 1, ry + n + 1) - ry - 1;
	for (int i = 1; i <= n; i++) {
		a[i].y = lower_bound(ry + 1, ry + _ + 1, a[i].y) - ry;
		if (mp[{a[i].x, ry[a[i].y]}] == i) vec[a[i].y].push_back(i);
	}
	// for (int i = 0; i < h; i++, eputs(""))
	// 	for (int j = 0; j < w; j++) eprintf("%d ", MAP[j][i]);

	for (int i = 1; i <= _; i++)
		sort(vec[i].begin(), vec[i].end(), [](const int &x, const int &y) {
			return a[x].x < a[y].x;
		});

	for (int i = 1; i <= _; i++) {
		for (int j = 0; j <= m; j++)
			for (int k = 0; k < (int)vec[i].size(); k++)
				for (int o = 0; o < 3; o++) {
					int now = vec[i][k];
					if (!o){
						dp[now][j][0] =
							max(dp[now][j][0], mx[0][j + a[now].x + 1000].query(w - a[now].x));
						dp[now][j][0] =
							max(dp[now][j][0], mx[1][j - a[now].x + 1000].query(a[now].x + 1));
					}

					if (dp[now][j][o] >= goal) {
						ans = min(ans, (long long)j * lrcost + (long long)ry[i] * dcost);
						// if (ans < 0x3f3f3f3f3f3f3f3f) eprintf("%d %d %d %d\n", now, j, o, dp[now][j][o]);
					}

					if (!o) {
						dp[now][j][1] = max(dp[now][j][1], dp[now][j][0] + a[now].v);
						dp[now][j][2] = max(dp[now][j][2], dp[now][j][0] + a[now].v);
					} else {
						if (o == 1 && k > 0) {
							int to = vec[i][k - 1];
							if (j + a[now].x - a[to].x <= m)
								dp[to][j + a[now].x - a[to].x][1] =
									max(dp[to][j + a[now].x - a[to].x][1], dp[now][j][1] + a[to].v);
						}
						if (o == 2 && k < (int)vec[i].size() - 1) {
							int to = vec[i][k + 1];
							if (j + a[to].x - a[now].x <= m)
								dp[to][j + a[to].x - a[now].x][2] =
									max(dp[to][j + a[to].x - a[now].x][2], dp[now][j][2] + a[to].v);
						}
					}
				}

		for (int j = 0; j <= m; j++)
			for (int k = 0; k < (int)vec[i].size(); k++)
				for (int o = 1; o < 3; o++) {
					int now = vec[i][k];
					mx[0][j + a[now].x + 1000].update(w - a[now].x, dp[now][j][o]);
					mx[1][j - a[now].x + 1000].update(a[now].x + 1, dp[now][j][o]);
				}
	}
	// eprintf("%d\n", dp[2][3][2]);
	if (ans == 0x3f3f3f3f3f3f3f3f) puts("-1");
	else printf("%lld\n", ans);
	return 0;
}

4.22

TopCoder PathGame

一个 2×n2 \times n 的网格，有若干障碍，两个人轮流操作，每次将一个空地变成障碍，要求操作后存在至少一条从左端到右端的路径，无法操作者输，求先手是否必胜。

考虑按障碍划分成若干区间，然后求每段的 SG 函数。对于非两端的区间，其起点和终点是确定的，并且若两边障碍在同一行，则其 SG 函数为 len mod 2len \bmod 2，否则为 1−len mod 21 - len \bmod 2。然后对于两端枚举障碍放在哪里暴力 DP 求 SG 函数即可。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <queue>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, a[3][1005], ans, dp[1005], b[1005];

int main() {
	scanf("%d", &n);
	{
		string s;
		cin >> s;
		n = s.length();
		for (int i = 0; i < n; i++) a[1][i + 1] = s[i] == '.';
	}
	{
		string s;
		cin >> s;
		n = s.length();
		for (int i = 0; i < n; i++) a[2][i + 1] = s[i] == '.';
	}
	for (int l = 1, r; l <= n; l = r + 1) {
		r = l;
		if (!a[1][l] || !a[2][l]) continue;
		while (r < n && a[1][r + 1] && a[2][r + 1]) r++;
		if (l != 1 && r != n) {
			int len = r - l + (a[1][l - 1] == a[1][r + 1]);
			ans ^= len & 1;
		}
		if (l == 1 && r == n) {puts(n % 2 ? "Snuke" : "Sothe"); return 0;}
	}
	dp[1] = 1;
	for (int i = 2; i <= n; i++) {
		memset(b, 0, sizeof(b));
		for (int j = 1; j <= i; j++) {
			if ((dp[j - 1] ^ ((i - j) & 1)) <= 1000) b[dp[j - 1] ^ ((i - j) & 1)] = 1;
			if (j < i && (dp[j - 1] ^ ((i - j - 1) & 1)) <= 1000) b[dp[j - 1] ^ ((i - j - 1) & 1)] = 1;
		}
		while (b[dp[i]]) dp[i]++;
	}
	int p = 1;
	while (a[1][p] && a[2][p]) p++;
	ans ^= dp[p - 1];
	p = n;
	while (a[1][p] && a[2][p]) p--;
	ans ^= dp[n - p];
	puts(ans ? "Snuke" : "Sothe");
	return 0;
}

TopCoder DengklekMessage

给定 01 串 ss 和 nn 个 01 串 tit_i，维护一个字符串 SS，初始为空，每次等概率从 tt 中选一个接在后面，操作 kk 次，问 ss 在 SS 中出现的次数的期望。

朴素想法是设 fi,jf_{i, j} 表示 ii 次操作，ss 匹配到 jj 的答案，再记一下到这个状态的概率，然后枚举这次拼哪个串转移，可以写成矩阵的形式，矩阵快速幂做到 O(∣s∣3log⁡k)O(|s|^3\log k)。

设 Fi=∑fiF_i = \sum f_i，其意义为 ii 次操作的答案，对 FF 差分，这样他的意义就变成了 ii 次操作，末尾在第 ii 个串内的次数，显然这个只会受前 ∣s∣|s| 个串的影响，因此 F∣s∣+1′=F∣s∣+2′=…=Fk′F'_{|s|+1} = F'_{|s|+2} = \ldots = F'_{k}，因此只需要做 ss 次就好了，复杂度为 O(∣s∣3)O(|s|^3)。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, m, nxt[505];
string s, t[55];
long long k;
double dp[505];
pair<double, double> operator*(const pair<double, double> &x, const pair<double, double> &y) {
	return make_pair(x.first * y.second + x.second * y.first, x.second * y.second);
}
pair<double, double> operator+(const pair<double, double> &x, const pair<double, double> &y) {
	return make_pair(x.first + y.first, x.second + y.second);
}
struct Matrix {
	int n, m;
	pair<double, double> mat[505][505];

	Matrix(int _n = 0, int _m = 0): n(_n), m(_m) {memset(mat, 0, sizeof(mat));}
	
	Matrix operator*(const Matrix &a) {
		Matrix ans(n, a.m);
		for (int i = 1; i <= n; i++)
			for (int k = 1; k <= m; k++)
				for (int j = 1; j <= a.m; j++)
					ans.mat[i][j] = ans.mat[i][j] + mat[i][k] * a.mat[k][j];
		return ans;
	}
} f, g;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) cin >> t[i];
	scanf("%d", &m);
	while (m--) {
		string ss;
		cin >> ss;
		s += ss;
	}
	m = s.length();
	s = " " + s;
	for (int i = 2, j = 0; i <= m; i++) {
		while (j && s[j + 1] != s[i]) j = nxt[j];
		if (s[j + 1] == s[i]) nxt[i] = ++j;
	}
	f.n = 1, f.m = m;
	f.mat[1][m].second = 1;
	g.n = g.m = m;
	for (int i = 1; i <= m; i++)
		for (int j = 1; j <= n; j++) {
			int now = i % m, cnt = 0;
			for (char k : t[j]) {
				while (now && s[now + 1] != k) now = nxt[now];
				if (s[now + 1] == k)
					if (++now == m) now = nxt[now], cnt++;
			}
			if (!now) now = m;
			// eprintf("%d %d %d\n", i, now, cnt);
			g.mat[i][now] = g.mat[i][now] + make_pair((double)cnt / n, 1. / n);
		}
	scanf("%lld", &k);
	for (int i = 1; i <= m + 1; i++) {
		f = f * g;
		for (int j = 1; j <= m; j++) dp[i] += f.mat[1][j].first;
	}
	if (k <= m) {printf("%.12lf\n", dp[k]); return 0;}
	// eprintf("%lf %lf\n", dp[2], dp[3]);
	// eprintf("%.12lf\n", dp[m]);
	double ans = dp[m] + (dp[m + 1] - dp[m]) * (k - m);
	printf("%.12lf\n", ans);
	return 0;
}

TopCoder RabbitPuzzle

数轴上有三只兔子，坐标为 (A,B,C)(A, B, C)，每次可以选两只兔子，将第一只兔子以第二只兔子为对称中心对称，要求不能跳过第三只兔子，问跳 kk 次到达目标坐标的方案数。

考虑有哪些跳法，分别是 (2A−B,A,C),(A,C,2C−B),(B,2B−A,C),(A,2B−C,B)(2A - B, A, C), (A, C, 2C - B), (B, 2B - A, C), (A, 2B - C, B)。其中后两种至多一种合法，并且当 B−A=C−BB - A = C - B 时均不合法。因此考虑对于每个状态，将他向通过前两种状态跳到的状态连一条边，则所有状态变成了若干棵满的无限高的二叉树，每个点可以跳到的状态就是他连接的点。

显然影响答案的只有起始点到 lca 的深度，终点到 lca 的深度和 lca 到根的深度，其中前两个超过 kk 则答案为 00，最后一个超过 kk 和等于 kk 时等价。

将最后一个转化成终点到根的深度，并且只移动起点，然后就可以 DP 了。
设 dpi,j,ldp_{i, j, l} 为起点和终点到 lca 的深度分别为 i,ji, j，走了 ll 步时的方案数，暴力转移即可。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <tuple>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 1e9 + 7;

long long sx, sy, sz, ex, ey, ez;
int n, dp[105][105][105];
vector<tuple<long long, long long, long long>> anc[2];

tuple<long long, long long, long long> getfa(tuple<long long, long long, long long> u) {
	long long A = get<0>(u), B = get<1>(u), C = get<2>(u);
	if (B - A == C - B) return {0, 0, 0};
	else if (B - A < C - B) return {B, 2 * B - A, C};
	else return {A, 2 * B - C, B};
}

int main() {
	scanf("%d%lld%lld%lld", &n, &sx, &sy, &sz);
	scanf("%d%lld%lld%lld", &n, &ex, &ey, &ez);
	scanf("%d", &n);
	anc[0].emplace_back(sx, sy, sz);
	for (int i = 1; i <= n; i++) {
		tuple<long long, long long, long long>fa = getfa(anc[0].back());
		if (get<0>(fa) == get<1>(fa)) break;
		anc[0].push_back(fa);
	}
	anc[1].emplace_back(ex, ey, ez);
	for (int i = 1; i <= n; i++) {
		tuple<long long, long long, long long>fa = getfa(anc[1].back());
		if (get<0>(fa) == get<1>(fa)) break;
		anc[1].push_back(fa);
	}
	// for (auto i : anc[0]) eprintf("%lld %lld %lld\n", get<0>(i), get<1>(i), get<2>(i));
	// eputs("");
	// for (auto i : anc[1]) eprintf("%lld %lld %lld\n", get<0>(i), get<1>(i), get<2>(i));
	int sdep = -1, tdep = -1;
	for (int i = 0; i < (int)anc[0].size(); i++) {
		for (int j = 0; j < (int)anc[1].size(); j++)
			if (anc[0][i] == anc[1][j]) {sdep = i; tdep = j; break;}
		if (sdep != -1) break;
	}
	// eprintf("%d %d\n", sdep, tdep);
	if (sdep == -1) {puts("0"); return 0;}
	// eputs("?");
	dp[0][sdep][tdep] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j <= n; j++)
			for (int k = 0; k <= n; k++) {
				if (j) dp[i][j + 1][k] = (dp[i][j + 1][k] + dp[i - 1][j][k] * 2ll) % mod;
				else {
					dp[i][j + 1][k] = (dp[i][j + 1][k] + dp[i - 1][j][k]) % mod;
					if (k) dp[i][j][k - 1] = (dp[i][j][k - 1] + dp[i - 1][j][k]) % mod;
					else dp[i][j + 1][k] = (dp[i][j + 1][k] + dp[i - 1][j][k]) % mod;
				}
				if (j) dp[i][j - 1][k] = (dp[i][j - 1][k] + dp[i - 1][j][k]) % mod;
				else if (k + 1 < (int)anc[1].size())
					dp[i][j][k + 1] = (dp[i][j][k + 1] + dp[i - 1][j][k]) % mod;
			}
	printf("%d\n", dp[n][0][0]);
	return 0;
}

4.23

训练赛盲盒终于开出一场质量较高的了。

TopCoder CycleColoring

有 nn 个环，第 ii 个环的长度为 LiL_i，每个环上的边是实边，另有 nn 条虚边，第 ii 条连接第 ii 个环上第 uiu_i 个点和第 (i+1) mod n(i + 1) \bmod n 个环上第 viv_i 个点。要给每个点染上 mm 种颜色中的一种，使得实边连接的两个点颜色不同，虚边连接的两个点颜色相同。

常规想法是钦定一个点的颜色然后往后递推，显然最好的方法是钦定第一个环上与最后一个环相连的点，然后一个环一个环推过去，这样每个环都会先钦定一个点其他任意，我们记 dpi,0/1dp_{i, 0 / 1} 表示考虑到第 ii 个环，与第 i−1i - 1 个环想连的点的颜色是 / 不是与最开始那个点的颜色相同，转移就考虑与第 i+1i + 1 个环相连的那个点的颜色，只需要求出长度为 ll 的链，钦定两端颜色，且这两端颜色相同 / 不相同时的方案数即可。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 1e9 + 7;

int n, c[55], u[55], v[55], k, f[1000005][2], g[1000005][3];

int F(int x) {return x == -1 ? 1 : f[x][0];}
int G(int x) {return x == -1 ? 0 : (g[x][0] + g[x][1]) % mod;}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &c[i]);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &u[i]);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &v[i]);
	scanf("%d", &k);
	f[0][1] = g[0][1] = 1; 
	for (int i = 1; i <= 1000000; i++) {
		f[i][0] = ((long long)f[i - 1][0] * (k - 2) + (long long)f[i - 1][1] * (k - 1)) % mod;
		f[i][1] = f[i - 1][0];
		g[i][0] = ((long long)g[i - 1][0] * (k - 3) + (long long)(g[i - 1][1] + g[i - 1][2]) * (k - 2)) % mod;
		g[i][1] = (g[i - 1][0] + g[i - 1][2]) % mod;
		g[i][2] = (g[i - 1][0] + g[i - 1][1]) % mod;
	}
	f[0][0] = 1;
	if (n == 1) {
		int a = min(abs(u[1] - v[n]), c[1] - abs(u[1] - v[n])) - 1, b = c[1] - a - 2;
		if (a) printf("%lld\n", (long long)F(a) * F(b) % mod * k % mod);
		else puts("0");
		return 0;
	}
	int dp[2] = {0, 0};
	{
		int a = min(abs(u[1] - v[n]), c[1] - abs(u[1] - v[n])) - 1, b = c[1] - a - 2;
		// eprintf("%d %d\n", u[1], v[n]);
		if (a != -1) dp[0] = (long long)G(a) * G(b) % mod * (k - 1) % mod;
		if (a) dp[1] = (long long)F(a) * F(b) % mod;
	}
	// eprintf("%d %d\n", dp[0], dp[1]);
	for (int i = 2; i <= n; i++) {
		int a = min(abs(u[i] - v[i - 1]), c[i] - abs(u[i] - v[i - 1])) - 1, b = c[i] - a - 2;
		int tmp[2] = {0, 0};
		if (a != -1) // diffrent
			tmp[0] = (long long)G(a) * G(b) % mod *
				(((long long)dp[1] * (k - 1) + (long long)dp[0] * (k - 2)) % mod) % mod;
		if (a) // same
			tmp[0] = (tmp[0] + (long long)F(a) * F(b) % mod * dp[0]) % mod;
		if (a != -1) tmp[1] = (long long)G(a) * G(b) % mod * dp[0] % mod; // diffrent
		// eprintf("%d %d %d\n", a, b, tmp[1]);
		if (a) tmp[1] = (tmp[1] + (long long)F(a) * F(b) % mod * dp[1]) % mod; // same
		dp[0] = tmp[0], dp[1] = tmp[1];
	}
	printf("%lld\n", (long long)dp[1] * k % mod);
	return 0;
}

TopCoder Egalitarianism2

平面上有 nn 个点，任意两个点之间的边的长度为欧几里德距离，求一棵生成树，使得边长的标准差最小。

考虑序列 a1,a2,…,an−1a_1, a_2, \ldots, a_{n - 1} 的标准差：

avg=1n−1∑i=1n−1aiσ=∑i=1n−1(avg−ai)2avgavg = \frac{1}{n - 1}\sum\limits_{i = 1}^{n - 1} a_i\\ \sigma = \sqrt{\frac{\sum\limits_{i = 1}^{n - 1}(avg - a_i)^2}{avg}}

显然只需要考虑 ∑i=1n−1(avg−ai)2\sum_{i = 1}^{n - 1}(avg - a_i)^2。

然后我们发现 f(x)=∑i=1n−1(x−ai)2f(x) = \sum_{i = 1}^{n - 1}(x - a_i)^2 在 x=avgx = avg 时取到最小值，因此可以将 avgavg 的条件放宽成任意实数，答案不变。

然后朴素想法就是枚举 xx 求最小生成树，剩下的问题就是怎么枚举。
发现求最小生成树时我们只关心每条边的大小关系，因此只需要考虑大小关系改变的时间点即可，而这些时间点就是任意两条边长度的平均数，因此总共只有 O(n4)O(n^4) 个时间点，直接来就是 O(n6log⁡n)O(n^6\log n)。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cmath>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, x[25], y[25], m, k;
struct edge {int u, v; double w;} e[405];
double w[160005], a[25], ans = 1e18;
struct dsu {
	int fa[25];

	void clear() {for (int i = 1; i < 25; i++) fa[i] = i;}
	int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
	void merge(int x, int y) {fa[find(x)] = find(y); return ;}
	int query(int x, int y) {return find(x) == find(y);}
} d;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &x[i]);
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &y[i]);
	for (int i = 1; i <= n; i++)
		for (int j = 1; j < i; j++)
			e[++m] = {i, j,
				sqrt((long long)(x[i] - x[j]) * (x[i] - x[j]) + (long long)(y[i] - y[j]) * (y[i] - y[j]))};
	for (int i = 1; i <= m; i++)
		for (int j = 1; j < i; j++) w[++k] = (e[i].w + e[j].w) / 2;
	for (int i = 1; i <= k; i++) {
		sort(e + 1, e + m + 1, [&](const edge &x, const edge &y) {
			return (w[i] - x.w) * (w[i] - x.w) < (w[i] - y.w) * (w[i] - y.w);
		});
		d.clear();
		int idx = 0;
		for (int j = 1; j <= m; j++)
			if (!d.query(e[j].u, e[j].v)) d.merge(e[j].u, e[j].v), a[++idx] = e[j].w;
		// eprintf("%.12lf\n", w[i]);
		// for (int i = 1; i <= idx; i++) eprintf("%lf ", a[i]);
		// eputs("");
		double avg = 0;
		for (int j = 1; j < n; j++) avg += a[j];
		avg /= n - 1;
		double res = 0;
		for (int j = 1; j < n; j++) res += (avg - a[j]) * (avg - a[j]);
		res = sqrt(res / (n - 1));
		ans = min(ans, res);
	}
	printf("%.12lf\n", ans);
	return 0;
}

TopCoder TheBoardingDivOne

懒得写题面了。

发现时间上限 222=74∗3222 = 74 * 3，因此如果一个人被阻挡两次就寄了，所以只需要考虑每个人至多被阻挡一次的情况。

考虑两个人 pi,pj,i<jp_i, p_j, i < j，如果 pip_i 到达终点的步数大于 pjp_j，则 pip_i 一定会被 pjp_j 直接或间接阻挡，也就是 pip_i 被阻挡的条件是 ∃j>i,pi+n−i>pj+n−j\exists j > i, p_i + n - i > p_j + n - j。

考虑从后往前 dp，设当前要往位置 ii 放 pp，记录已经确定的步数最小值为 mnmn，则当 p+n−i≤mnp + n - i \le mn 时可以直接放置，否则设当前还未确定的里面最大值为 mm，若 p<mp < m，则 mm 在 pp 等待 mnmn 时会被阻挡一次，在 pp 入座时又会阻挡一次，就不合法了，因此此时必须满足 p=mp = m。

然后就直接暴力 dp 就好了。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, p[25], limit;
long long dp[1 << 18][45];

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &p[i]);
	scanf("%d", &limit);
	for (int i = 1; i <= n; i++)
		if (p[n] == -1 || p[n] == i)
			if (i <= limit - 74) dp[1 << (i - 1)][i] = 1;
	for (int S = 1; S < 1 << n; S++)
		for (int mn = 1; mn <= min(limit - 74, 2 * n - 1); mn++) {
			int pos = n - __builtin_popcount(S);
			for (int i = n, flag = 1; i >= 1; i--)
				if (!(S >> (i - 1) & 1)) {
					// eprintf("%d %d\n", S, i);
					if (p[pos] == -1 || p[pos] == i) {
						int cost = n + i - pos + 74;
						if (n + i - pos > mn) cost += 74;
						if (cost <= limit && (n + i - pos <= mn || flag))
							dp[S | 1 << (i - 1)][min(n + i - pos, mn)] += dp[S][mn];
					}
					flag = 0;
				}
		}
	// eprintf("%lld\n", dp[3][2]);
	long long ans = 0;
	for (int i = 1; i <= min(limit - 74, 2 * n - 1); i++) ans += dp[(1 << n) - 1][i];
	printf("%lld\n", ans);
	return 0;
}

TopCoder TheCitiesAndRoadsDivOne

给你一张图，你要补上一些边使得图变成一棵基环树或树，求方案数。

枚举环上的点，然后环的方案数是好求的，接下来就是把环缩成一个连通块，然后变成 nn 个点有若干个连通块连成树的方案树，这个是经典结论，设有 mm 个连通块，每个连通块大小为 did_i，则答案为：

nm−2∑i=1mdin^{m - 2}\sum\limits_{i = 1}^m d_i

然后就做完了。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 1234567891, inv2 = 617283946;

int n, g[25], m, ans;
struct edge {int u, v;} e[405];
struct dsu {
	int fa[25], cnt[25];

	void clear() {for (int i = 0; i < 25; i++) fa[i] = i, cnt[i] = 1; return ;}
	int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
	void merge(int x, int y) {
		int fx = find(x), fy = find(y);
		if (fx == fy) return ;
		cnt[fy] += cnt[fx];
		fa[find(x)] = find(y);
		return ;
	}
	int query(int x, int y) {return find(x) == find(y);}
} d;

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {
			char c;
			cin >> c;
			if (c == 'Y') g[i] |= 1 << j, g[j] |= 1 << i;
			if (c == 'Y' && i < j) e[++m] = {i, j};
		}
	if (m > n) {puts("0"); return 0;}
	{
		int flag = 1;
		d.clear();
		for (int i = 1; i <= m; i++)
			if (d.query(e[i].u, e[i].v)) flag = 0;
			else d.merge(e[i].u, e[i].v);
		ans = 1;
		int cnt = 0;
		for (int i = 0; i < n; i++)
			if (d.find(i) == i) ans = (long long)ans * d.cnt[i] % mod, cnt++;
		for (int i = 1; i <= cnt - 2; i++) ans = (long long)ans * n % mod;
		if (cnt == 1) ans = 1;
		ans *= flag;
		// eprintf("%d\n", ans);
	}
	for (int S = 1; S < 1 << n; S++) if (__builtin_popcount(S) > 2) {
		int flag = 1, c = 0;
		d.clear();
		for (int i = 0; i < n; i++)
			if (S >> i & 1) {
				if (__builtin_popcount(g[i] & S) > 2) flag = 0;
				for (int T = g[i] & S; T; T -= T & -T) {
					int j = __builtin_ctz(T);
					if (i > j) continue;
					if (d.query(i, j)) c = 1;
					d.merge(i, j);
				}
			}
		// eprintf("%d %d\n", S, flag);
		if (!flag) continue;
		int res = 1, cnt = 0;
		for (int i = 0; i < n; i++)
			if (S >> i & 1 && d.find(i) == i) res = (long long)res * (1 + (d.cnt[i] > 1)) % mod, cnt++;
		if (cnt > 1 && c) continue;
		for (int i = 1; i < cnt; i++) res = (long long)res * i % mod;
		res = (long long)res * inv2 % mod;
		for (int i = 0; i < n; i++)
			if (S >> i & 1) d.merge(i, __builtin_ctz(S));
		for (int i = 1; i <= m; i++)
			if (!(S >> e[i].u & 1) || !(S >> e[i].v & 1)) {
				// eputs("?");
				// if (S == 7) eprintf("%d %d\n", e[i].u, e[i].v);
				if (d.query(e[i].u, e[i].v)) flag = 0;
				else d.merge(e[i].u, e[i].v);
			}
		if (!flag) continue;
		cnt = 0;
		int tmp = 1;
		for (int i = 0; i < n; i++)
			if (d.find(i) == i) tmp = (long long)tmp * d.cnt[i] % mod, cnt++;
		for (int i = 1; i <= cnt - 2; i++) tmp = (long long)tmp * n % mod;
		// eprintf("%d %d\n", S, d.find(0));
		if (cnt > 1) res = (long long)res * tmp % mod;
		ans = ((long long)ans + res) % mod;
	}
	printf("%d\n", ans);
	return 0;
}

TopCoder VerySmoothDecompositions

给一个大整数，求有多少种方法将这个数表示成 ∏i=216iki\prod_{i = 2}^{16} i^{k_i} 的形式。

先求出 2,3,5,7,11,132, 3, 5, 7, 11, 13 每个质因子各有多少。

11,1311, 13 无法和别的质数组合因此分解方法唯一，不需要考虑。

5,75, 7 有 5,7,2×5,3×5,2×75, 7, 2 \times 5, 3 \times 5, 2 \times 7 这几种，枚举分配给 5,75, 7 的 2,32, 3 的个数，可以 O(1)O(1) 求出答案。

2,32, 3 有 2,22,23,24,3,32,2×3,22×32, 2^2, 2^3, 2^4, 3, 3^2, 2\times 3, 2^2\times 3 这几种，直接背包求 fi,jf_{i, j} 表示有 ii 个 22，jj 个 33 的方案数即可。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 1e9 + 9;

int n, a[2505];
int n2, n3, n5, n7;
int  two[8405], three[5305], dp[8405][5305];
string s;

int check(int x) {
	int mod = 0;
	for (int i = n - 1; i >= 0; i--) {
		mod = mod * 10 + a[i];
		mod %= x;
	}
	return !mod;
}
void div(int x) {
	int mod = 0;
	for (int i = n - 1; i >= 0; i--) {
		mod = mod * 10 + a[i];
		a[i] = mod / x;
		mod %= x;
	}
	while (!a[n - 1]) n--;
	return ;
}

int main() {
	scanf("%d", &n);
	while (n--) {
		string ss;
		cin >> ss;
		s += ss;
	}
	n = s.length();
	for (int i = 0; i < n; i++) a[i] = s[n - i - 1] - '0';
	// for (int i = n - 1; i >= 0; i--) eprintf("%d", a[i]);
	// eputs("");
	while (check(2)) div(2), n2++;
	while (check(3)) div(3), n3++;
	while (check(5)) div(5), n5++;
	while (check(7)) div(7), n7++;
	while (check(11)) div(11);
	while (check(13)) div(13);
	if (n > 1 || a[0] != 1) {puts("0"); return 0;}
	// eprintf("%d %d %d %d\n", n2, n3, n5, n7);
	two[0] = 1;
	for (int i = 1; i <= 4; i++)
		for (int j = i; j <= n2; j++) two[j] = (two[j] + two[j - i]) % mod;
	three[0] = 1;
	for (int i = 1; i <= 2; i++)
		for (int j = i; j <= n3; j++) three[j] = (three[j] + three[j - i]) % mod;
	for (int i = 0; i <= n2; i++)
		for (int j = 0; j <= n3; j++) dp[i][j] = (long long)two[i] * three[j] % mod;
	for (int i = 1; i <= n2; i++)
		for (int j = 1; j <= n3; j++) dp[i][j] = (dp[i][j] + dp[i - 1][j - 1]) % mod;
	for (int i = 2; i <= n2; i++)
		for (int j = 1; j <= n3; j++) dp[i][j] = (dp[i][j] + dp[i - 2][j - 1]) % mod;
	int ans = 0;
	for (int i = 0; i <= n2; i++)
		for (int j = 0; j <= n3; j++) {
			if (j > n5 || i > n5 - j + n7) continue;
			// eprintf("%d %d\n", i, j);
			ans = (ans + (long long)dp[n2 - i][n3 - j] * (min(n5 - j, i) - max(0, i - n7) + 1)) % mod;
		} // x, i - x : 0 <= x <= n5 - j, i >= x >= i - n7
	printf("%d\n", ans);
	return 0;
}

4.26

A

有一个 77 位字符串，字符集为 55，给定 nn 条限制，每条限制限定每一位大于或小于或等于某个字符，所有限制可以推出矛盾。以任意顺序给出这些限制，在这些限制出现矛盾时停止，问在 1∼n1 \sim n 时刻停止的本质不同的方案数。

把限制看作超立方体，矛盾就是超立方体无交。

显然出现矛盾的一定是两条限制，考虑在不矛盾的限制之间连边，设 fif_i 为大小为 ii 的团的数量，则 ii 的答案就是 fi−1×(i−1)!×(n−i+1)−fi×i!f_{i - 1} \times (i - 1)! \times (n - i + 1) - f_i \times i!。

然后考虑这个东西怎么求，最直接的想法就是枚举交的右上角，容斥钦定若干维没有取到最大值，那就是选择的超立方体必须包含某个 每一维长度为 00 或 11的超立方体，直接枚举，这样复杂度是 O(5727n)O(5^7 2 ^ 7 n)。

首先超立方体的大小不确定比较难搞，那就对于长度为 11 的维度将 nn 个超立方体的这一维右端点减一，这样所有询问都变成了一个点。

把容斥提到最外层，因为我们要求所有点的答案之和，因此可以用高维差分和前缀和求出包含每个点的超立方体的个数。这样复杂度就是 O(47n+2757)O(4^7 n + 2^7 5^7)。

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
105
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 998244353;

int n, l[5005][7], r[5005][7], f[5005], a[6][6][6][6][6][6][6], num[5005];
int fac[5005], inv[5005];
string s[5005], op[5005];

int C(int n, int m) {return n < m ? 0 : (long long)fac[n] * inv[m] % mod * inv[n - m] % mod;}

int main() {
	freopen("topcoder.in", "r", stdin);
	freopen("topcoder.out", "w", stdout);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> s[i];
	cin >> n;
	for (int i = 1; i <= n; i++) cin >> op[i];
	fac[0] = fac[1] = 1;
	inv[0] = inv[1] = 1;
	for (int i = 2; i <= n; i++) {
		fac[i] = (long long)fac[i - 1] * i % mod;
		inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
	}
	for (int i = 2; i <= n; i++) inv[i] = (long long)inv[i - 1] * inv[i] % mod;
	for (int i = 1; i <= n; i++)
		for (int k = 0; k < 7; k++) {
			if (op[i][k] == '+') l[i][k] = 0, r[i][k] = s[i][k] - 'A' - 1;
			else if (op[i][k] == '-') l[i][k] = s[i][k] - 'A' + 1, r[i][k] = 4;
			else l[i][k] = r[i][k] = s[i][k] - 'A';
		}
	for (int S = 0; S < 1 << 7; S++) {
		memset(a, 0, sizeof(a));
		for (int i = 1; i <= n; i++) {
			int flag = 1;
			for (int j = 0; j < 7; j++)
				if (l[i][j] > r[i][j] - (S >> j & 1)) {flag = 0; break;}
			if (!flag) continue;
			for (int T = 0; T < 1 << 7; T++) {
				int b[7];
				for (int j = 0; j < 7; j++)
					if (T >> j & 1) b[j] = r[i][j] - (S >> j & 1) + 1;
					else b[j] = l[i][j];
				if (__builtin_popcount(T) % 2 == 0)
					a[b[0]][b[1]][b[2]][b[3]][b[4]][b[5]][b[6]]++;
				else
					a[b[0]][b[1]][b[2]][b[3]][b[4]][b[5]][b[6]]--;
			}
		}
		for (int i = 0; i < 7; i++) {
			int j[7];
			for (j[0] = i == 0; j[0] < 5; j[0]++)
				for (j[1] = i == 1; j[1] < 5; j[1]++)
					for (j[2] = i == 2; j[2] < 5; j[2]++)
						for (j[3] = i == 3; j[3] < 5; j[3]++)
							for (j[4] = i == 4; j[4] < 5; j[4]++)
								for (j[5] = i == 5; j[5] < 5; j[5]++)
									for (j[6] = i == 6; j[6] < 5; j[6]++) {
										int k[7];
										memcpy(k, j, sizeof(k));
										k[i]--;
										a[j[0]][j[1]][j[2]][j[3]][j[4]][j[5]][j[6]] +=
											a[k[0]][k[1]][k[2]][k[3]][k[4]][k[5]][k[6]];
									}
		}
		int l[7] = {5, 5, 5, 5, 5, 5, 5};
		for (int i = 0; i < 7; i++) l[i] -=S >> i & 1;
		int j[7];
		for (j[0] = 0; j[0] < l[0]; j[0]++)
			for (j[1] = 0; j[1] < l[1]; j[1]++)
				for (j[2] = 0; j[2] < l[2]; j[2]++)
					for (j[3] = 0; j[3] < l[3]; j[3]++)
						for (j[4] = 0; j[4] < l[4]; j[4]++)
							for (j[5] = 0; j[5] < l[5]; j[5]++)
								for (j[6] = 0; j[6] < l[6]; j[6]++) {
									// eprintf("%d %d\n", S, a[j[0]][j[1]][j[2]][j[3]][j[4]][j[5]][j[6]]);
									if (__builtin_popcount(S) % 2 == 0)
										num[a[j[0]][j[1]][j[2]][j[3]][j[4]][j[5]][j[6]]]++;
									else
										num[a[j[0]][j[1]][j[2]][j[3]][j[4]][j[5]][j[6]]]--;
								}
	}
	for (int i = 1; i <= n; i++)
		for (int j = 1; j <= i; j++)
			f[j] = ((f[j] + (long long)num[i] * C(i, j)) % mod + mod) % mod;
	f[0] = 1;
	for (int i = 1; i <= n; i++) {
		int ansa = (long long)f[i - 1] * fac[i - 1] % mod * (n - i + 1) % mod;
		int ansb = (long long)f[i] * fac[i] % mod;
		cout << (ansa - ansb + mod) % mod << ' ';
	}
	cout << '\n';
	return 0;
}

B

给定 n,k,mn, k, m，求：

∑∣S∣=kS⊆{m+1,m+2,…,n−1}∏x∈Sx mod n\sum\limits_{\substack{|S| = k\\ S \subseteq \{m + 1, m + 2, \ldots, n - 1\}}} \prod\limits_{x \in S} x \bmod n

nn 为素数，1≤k<n−11 \le k < n - 1。

先考虑 m=0m = 0 的情况。

设：

X=∑∣S∣=tS⊆{m+1,m+2,…,n}∏x∈Sx,1≤t<n−1X = \sum\limits_{\substack{|S| = t\\ S \subseteq \{m + 1, m + 2, \ldots, n\}}} \prod\limits_{x \in S} x, 1 \le t < n - 1

取模 nn 的原根 gg，则：

∑∣S∣=tS⊆{m+1,m+2,…,n}∏x∈Sgx≡gt∑∣S∣=tS⊆{m+1,m+2,…,n}∏x∈Sx=gtX(modn)\sum\limits_{\substack{|S| = t\\ S \subseteq \{m + 1, m + 2, \ldots, n\}}} \prod\limits_{x \in S} gx \equiv g^t \sum\limits_{\substack{|S| = t\\ S \subseteq \{m + 1, m + 2, \ldots, n\}}} \prod\limits_{x \in S} x = g^t X \pmod n

容易发现 gt≠1g^t \ne 1，因此 X=0X = 0。

然后考虑更一般的情况，答案为：

[xk]∏i=m+1n−1(1+ix)=[xk]∏1n−1(1+ix)∏1m(1+ix)≡[xk]1−xn−1∏1m(1+ix)(modn)=[xk]1∏1m(1+ix)=(−1)k[xk]1∏1m(1−ix)=(−1)k{k+mm}=∑i=0mik+m(−1)m−i+ki!(m−i)!\begin{aligned} [x^k]\prod_{i = m + 1}^{n - 1} (1 + ix) &= [x^k] \frac{\prod_1^{n - 1} (1 + ix)}{\prod_1^{m} (1 + ix)} \\ &\equiv [x^k] \frac{1 - x^{n - 1}}{\prod_1^{m} (1 + ix)} \pmod n \\ &= [x^k] \frac{1}{\prod_1^{m} (1 + ix)} \\ &= (-1)^k [x^k] \frac{1}{\prod_1^{m} (1 - ix)} \\ &= (-1)^k {k + m \brace m} \\ &= \sum\limits_{i = 0}^m \frac{i^{k + m}(-1)^{m - i + k}}{i!(m - i)!} \end{aligned}

其中倒数第二步可以参考这个，最后一步是斯特林数通项公式。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, k, m, fac[20000005], inv[20000005];
int cnt, prime[20000005], f[20000005], pw[20000005];
int ans;

int power(int a, int b) {
	int ans = 1;
	while (b) {
		if (b & 1) ans = (long long)ans * a % n;
		a = (long long)a * a % n;
		b >>= 1;
	}
	return ans % n;
}

int main() {
	freopen("wzdndjl.in", "r", stdin);
	freopen("wzdndjl.out", "w", stdout);
	scanf("%d%d%d", &n, &k, &m);
	fac[0] = fac[1] = 1;
	inv[0] = inv[1] = 1;
	for (int i = 2; i <= m; i++) {
		fac[i] = (long long)fac[i - 1] * i % n;
		inv[i] = (long long)(n - n / i) * inv[n % i] % n;
	}
	for (int i = 2; i <= m; i++) inv[i] = (long long)inv[i - 1] * inv[i] % n;
	pw[1] = 1;
	for (int i = 2; i <= m; i++) {
		if (!f[i]) pw[i] = power(i, m + k), prime[++cnt] = i;
		for (int j = 1; j <= cnt && prime[j] <= m / i; j++) {
			f[prime[j] * i] = 1;
			pw[prime[j] * i] = (long long)pw[prime[j]] * pw[i] % n;
			if (i % prime[j] == 0) break;
		}
	}
	// for (int i = 0; i <= m; i++) eprintf("%d ", inv[i]);
	// eputs("");
	for (int i = 0; i <= m; i++)
		if ((m - i + k) % 2 == 0) ans = (ans + (long long)pw[i] * inv[i] % n * inv[m - i]) % n;
		else ans = (ans - (long long)pw[i] * inv[i] % n * inv[m - i] % n + n) % n;
	printf("%d\n", ans);
	return 0;
}

4.28

B

给一张 nn 个点 mm 条边的带权无向图，你要钦定 kk 条边，使得包含这 kk 条边的最小生成树最大。

设 dpS,idp_{S, i} 为点集 SS 中钦定 ii 条边的答案，每次枚举一个子集钦定最大生成树转移，问题是集合间的边怎么选。

考虑 Prim，对于当前集合 SS，找到与之最近的点 uu，令枚举的集合必须包含 uu 即可。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, m, k, dp[1 << 16][16], f[1 << 16];
struct edge {int u, v, w;} e[125], ee[125];
struct dsu{
	int fa[16];

	dsu() {for (int i = 0; i < 16; i++) fa[i] = i;}
	int find(int x) {return x == fa[x] ? x : fa[x] = find(fa[x]);}
	void merge(int x, int y) {fa[find(x)] = find(y); return ;}
	int query(int x, int y) {return find(x) == find(y);}
} d;

int main() {
	scanf("%d%d%d", &n, &m, &k);
	for (int i = 1; i <= m; i++)
		scanf("%d%d%d", &e[i].u, &e[i].v, &e[i].w), e[i].u--, e[i].v--;
	sort(e + 1, e + m + 1, [](const edge &x, const edge &y) {return x.w < y.w;});
	for (int S = 1; S < 1 << n; S++) {
		dsu d;
		for (int i = m; i >= 1; i--)
			if (S >> e[i].u & 1 && S >> e[i].v & 1 && !d.query(e[i].u, e[i].v))
				f[S] += e[i].w, d.merge(e[i].u, e[i].v);
	}
	{
		dsu d;
		int idx = 0;
		for (int i = 1; i <= m; i++)
			if (!d.query(e[i].u, e[i].v)) ee[++idx] = e[i], d.merge(e[i].u, e[i].v);
		memcpy(e, ee, sizeof(e));
	}
	// for (int i = 1; i < n; i++) eprintf("%d %d %d\n", e[i].u, e[i].v, e[i].w);
	memset(dp, ~0x3f, sizeof(dp));
	dp[0][0] = 0;
	for (int i = 0; i <= k; i++)
		for (int S = 0; S < 1 << n; S++) {
			if (i == __builtin_popcount(S) - 1) dp[S][i] = f[S];
			if (dp[S][i] == ~0x3f3f3f3f) continue;
			int to = 0, val = 0x3f3f3f3f;
			for (int j = 1; j < n; j++)
				if (S >> e[j].u & 1 && !(S >> e[j].v & 1)) {
					if (e[j].w < val) to = e[j].v, val = e[j].w;
				} else if (S >> e[j].v & 1 && !(S >> e[j].u & 1)) {
					if (e[j].w < val) to = e[j].u, val = e[j].w;
				}
			// if (S == 7) eprintf("%d\n", to);
			int T = ((1 << n) - 1) ^ S;
			for (int TT = T; TT; TT = (TT - 1) & T) {
				if (!(TT & 1 << to) && S) continue;
				int V = dp[S][i] + f[TT] + val;
				dsu d;
				dp[S | TT][i + __builtin_popcount(TT) - 1] =
					max(dp[S | TT][i + __builtin_popcount(TT) - 1], V);
			}
		}
	// eprintf("%d\n", dp[7][0]);
	printf("%d\n", dp[(1 << n) - 1][k]);
	return 0;
}

C

令第 ii 个人在状态 ss 中的答案为 ixorrev(s)i \mathbin{\mathrm{xor}} \mathrm{rev}(s) 即可，其中 rev(s)\mathrm{rev}(s) 为 ss 的逆序对个数。

证明考虑设整个状态为 s=s1s2…sns = s_1 s_2 \ldots s_n，逆序对个数为 invinv，则：

  • si=0s_i = 0 时，输出的值为 i+inv−∑j=1i−1[sj=1]≡inv+∑j=1i[sj=0](mod2)i + inv - \sum_{j = 1}^{i - 1} [s_j = 1] \equiv inv + \sum_{j = 1}^i [s_j = 0] \pmod 2
  • si=1s_i = 1 时，输出的值为 i+inv−∑j=i+1n[sj=0]≡inv+n−∑j=i+1n[sj=1](mod2)i + inv - \sum_{j = i + 1}^n [s_j = 0] \equiv inv + n - \sum_{j = i + 1}^n [s_j = 1] \pmod 2

因此把 00 扣出来后输出 0101 交替，把 11 扣出来后输出 0101 交替，也就是说两种颜色都是要么第奇数个全对要么第偶数个全对，这样就满足要求了。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++, puts(""))
		for (int S = 0; S < 1 << (n - 1); S++) {
			int res = i;
			for (int T = S; T; T >>= 1)
				if (!(T & 1)) res ^=__builtin_popcount(T);
			putchar('B' + (res & 1));
		}
	return 0;
}

4.29

A

有 nn 个灯，前 vv 个是开着的，每次可以选择若干个位置将状态反转，问选 mm 种本质不同的操作使得最终灯全关掉的方案数。

设 fif_i 为有顺序操作 ii 次的方案数，则：

fi={[v=0]i=01i=1(2n)i−1‾−fi−2(2n−i+2)(i−1)otherwise.f_i = \begin{cases} [v = 0] & i = 0 \\ 1 & i = 1 \\ (2^n)^{\underline{i - 1}} - f_{i - 2}(2^n - i + 2)(i - 1) & \text{otherwise.} \end{cases}

不过考场上不是这么写的，可以通过打表观察到 v>0v > 0 时答案相同，因此只需要算 v=0v = 0 的答案，然后就是：

fi={1i<=1(2ni−1)−fi−2(2n−i+2)iotherwise.f_i = \begin{cases} 1 & i <= 1 \\ \frac{\binom{2^n}{i - 1} - f_{i - 2}(2^n - i + 2)}{i} & \text{otherwise.} \end{cases}

本质相同。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 19260817;

int T, n, m, v, inv[1005], C[1005], dp[1005];

int power(int a, int b) {
	int ans = 1;
	while (b) {
		if (b & 1) ans = (long long)ans * a % mod;
		a = (long long)a * a % mod;
		b >>= 1;
	}
	return ans % mod;
}

int main() {
	inv[0] = inv[1] = 1;
	for (int i = 2; i <= 1000; i++) inv[i] = (long long)(mod - mod / i) * inv[mod % i] % mod;
	// for (int i = 2; i <= 1000; i++) inv[i] = (long long)inv[i - 1] * inv[i] % mod;
	scanf("%d", &T);
	while (T--) {
		scanf("%d%d%d", &n, &m, &v);
		int pw = power(2, n);
		C[0] = 1;
		for (int i = 1; i <= m; i++) C[i] = (long long)C[i - 1] * (pw - i + 1) % mod * inv[i] % mod;
		dp[0] = dp[1] = 1;
		for (int i = 2; i <= m; i++)
			dp[i] = (C[i - 1] - (long long)dp[i - 2] * (pw - i + 2 + mod) % mod + mod) * inv[i] % mod;
		// eprintf("%lld\n", dp[m]);
		if (!v) {printf("%d\n", dp[m]); continue;}
		int ans = (C[m] - dp[m] + mod) % mod;
		// eprintf("%d\n", (pw + mod - 1) % mod);
		ans = (long long)ans * power((pw + mod - 1) % mod, mod - 2) % mod;
		printf("%d\n", ans);
	}
	return 0;
}

B TopCoder StringDecryption

将一个数字串进行一次加密：找出所有极长连续段，将其变成长度 + 这个数字。

给出一个二次加密后的串，求原串方案数。

就按题意 DP……

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 1e9 + 9;

int n, a[505], dp[505][11][2];
string s;

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		string t;
		cin >> t;
		s += t;
	}
	n = s.length();
	s = " " + s;
	for (int i = 1; i <= n; i++) a[i] = s[i] - '0';
	dp[0][10][0] = 1;
	for (int i = 1; i <= n; i++)
		for (int j = 0; j < i - 1; j++) if (a[j] != a[i] && a[j + 1]) {
			int num = 0;
			for (int k = j + 1; k < i; k++) num = (num * 10ll + a[k]) % mod;
			for (int k = 0; k <= 10; k++) {
				if (a[i]) dp[i][k][1] = (dp[i][k][1] + dp[j][k][0]) % mod;
				dp[i][k][1] = (dp[i][k][1] + dp[j][k][1]) % mod;
				if (a[i] != k) {
					if (a[i]) {
						if (j != i - 2 || num != 1)
							dp[i][a[i]][1] =
								(dp[i][a[i]][1] + (long long)(num + mod - 2) * dp[j][k][0]) % mod;
						dp[i][a[i]][1] = (dp[i][a[i]][1] + (long long)(num + mod - 1) * dp[j][k][1]) % mod;
					}
					dp[i][a[i]][0] = (dp[i][a[i]][0] + dp[j][k][1]) % mod;
					if (a[i] && (j != i - 2 || num != 1))
						dp[i][a[i]][0] = (dp[i][a[i]][0] + dp[j][k][0]) % mod;
				}
			}
		}
	printf("%d\n", dp[n][a[n]][0]);
	return 0;
}

C

nn 个集合编号 1∼n1\sim n，初始为空，每次操作为给区间 [l,r][l, r] 内的集合添加一个 xx，或查询 max⁡i=lrmexSi\max_{i = l}^r \mathrm{mex} S_i。强制在线。

正着维护有的数很困难，考虑维护没有的数，这样 mex\mathrm{mex} 就变成了集合最小值。

考虑对每个数开一棵线段树，然后将信息维护在尽量上的点上，具体地，考虑给每个点一个颜色，黑色表示整个区间都有这个数，白色表示整个区间都没有这个数，剩下的是灰色，那么我们只要在所有是白色且父亲是灰色的点上维护信息即可，这样一个点的实际答案就是他到根的链上有信息的最小值。

观察修改操作，发现最多添加 O(log⁡n)O(\log n) 个点，因此所有线段树的总点数是 O(nlog⁡n)O(n\log n) 的，那就把所有信息扔同一棵线段树上，然后每个点的实际答案就是他到根的集合的并的最小值。

修改的加点问题解决了，还要解决删点问题。发现如果一次操作覆盖了线段树上某个节点，则要将整棵子树的这个数都删掉，直接来肯定不行。但是当修改不交时每次覆盖一个点时其子树内必然只有这个点可能有这个数，因此用 ODT 之类的把询问拆成若干个不交的区间即可。

然后考虑查询，对于每个点维护子树内的答案，pushup 时两边取 max⁡\max 再和当前节点的集合的最小值取 min⁡\min 即可。

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <cassert>
#include <iostream>
#include <algorithm>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;
using namespace __gnu_pbds;

const int n = 2e5;

int q;
long long anssum;
set<pair<int, int>> s[200005];
struct SegmentTree {
#define ls(x) (x * 2)
#define rs(x) (x * 2 + 1)

	int mx[800005];
	set<int> s[800005];
	int l[800005], r[800005];

	void build(int ll, int rr, int now = 1) {
		mx[now] = 0x3f3f3f3f, s[now].insert(0x3f3f3f3f);
		if (now == 1) {
			mx[now] = 0;
			for (int i = 0; i <= 100000; i++) s[now].insert(i);
		}
		l[now] = ll, r[now] = rr;
		if (ll == rr) return ;
		int mid = (ll + rr) / 2;
		build(ll, mid, ls(now)), build(mid + 1, rr, rs(now));
		return ;
	}
	void update(int ll, int rr, int val, int pl, int pr, int now = 1) {
		if (ll > rr) return ;
		assert(ll <= rr);
		s[now].erase(val);
		if (ll <= l[now] && r[now] <= rr) {
			if (l[now] != r[now])
				mx[now] = min(max(mx[ls(now)], mx[rs(now)]), *s[now].begin());
			else mx[now] = *s[now].begin();
			return ;
		}
		int mid = (l[now] + r[now]) / 2;
		if (ll <= mid) update(ll, rr, val, pl, pr, ls(now));
		else {
			if (max(l[ls(now)], pl) <= min(r[ls(now)], pr));
			else {
				auto it = ::s[val].upper_bound({r[ls(now)] + 1, 0});
				if (it != ::s[val].begin() && prev(it)->second >= l[ls(now)]);
				else mx[ls(now)] = min(mx[ls(now)], val), s[ls(now)].insert(val);
			}
		}
		if (mid < rr) update(ll, rr, val, pl, pr, rs(now));
		else {
			if (max(l[rs(now)], pl) <= min(r[rs(now)], pr));
			else {
				auto it = ::s[val].upper_bound({r[rs(now)] + 1, 0});
				if (it != ::s[val].begin() && prev(it)->second >= l[rs(now)]);
				else mx[rs(now)] = min(mx[rs(now)], val), s[rs(now)].insert(val);
			}
		}
		mx[now] = min(max(mx[ls(now)], mx[rs(now)]), *s[now].begin());
		// eprintf("%d %d %d %d %d %d\n", val, l[now], r[now], mx[now], mx[ls(now)], mx[rs(now)]);
		return ;
	}
	int query(int ll, int rr, int now = 1) {
		assert(ll <= rr);
		// eprintf("%d %d %d\n", l[now], r[now], mx[now]);
		if (ll <= l[now] && r[now] <= rr) return mx[now];
		int mid = (l[now] + r[now]) / 2, res = 0;
		if (ll <= mid) res = max(res, query(ll, rr, ls(now)));
		if (mid < rr) res = max(res, query(ll, rr, rs(now)));
		return min(res, *s[now].begin());
	}

#undef ls
#undef rs
} tr;

int main() {
	freopen("mex.in", "r", stdin);
	freopen("mex.out", "w", stdout);
	tr.build(0, n);
	scanf("%d", &q);
	while (q--) {
		int op;
		scanf("%d", &op);
		if (op == 1) {
			long long x, l, r;
			scanf("%lld%lld%lld", &x, &l, &r);
			x ^= anssum, l ^= anssum, r ^= anssum;
			// eprintf("[%lld, %lld]: %lld\n", l, r, x);
			if (x > 100000) continue;
			auto it = s[x].lower_bound({l, 0});
			if ((it == s[x].end() || it->first != l) && it != s[x].begin()) {
				it = prev(it);
				if (l <= it->second) l = it->second + 1;
			}
			int ll = l;
			while (l <= r) {
				auto it = s[x].lower_bound({l, 0});
				if (it == s[x].end() || it->first > r) break;
				tr.update(l, it->first - 1, x, ll, max(l - 1, r));
				l = it->second + 1;
				s[x].erase(it);
			}
			if (l <= r) tr.update(l, r, x, ll, max(l - 1, r));
			if (ll <= max(l - 1, r)) s[x].emplace(ll, max(l - 1, r));
		} else {
			long long l, r;
			scanf("%lld%lld", &l, &r);
			l ^= anssum, r ^= anssum;
			int ans = tr.query(l, r);
			printf("%d\n", ans);
			anssum += ans;
		}
	}
	return 0;
}
/*
14
2 1 3
1 0 2 6
1 0 4 7
1 0 15 20
1 1 6 12
2 1 5
2 7 7
2 11 15
1 1 3 819
2 1 100
1 6 302 462
1 7 400 500
1 5 350 550
2 462 500

*/

D

有 nn 个数，每次可以选两个数删掉并添加它们的平均数，求一种方案使得最终只剩一个数或返回无解。

嗯随，每次随机两个合法的操作，随 400 次。正确性未知。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <chrono>
#include <random>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

mt19937 gen(chrono::system_clock::now().time_since_epoch().count());

int T, n;
long long a[1000005];
vector<pair<long long, long long>> ans;

int check() {
	vector<long long> vec[2];
	for (int i = 1; i <= n; i++) vec[a[i] & 1].push_back(a[i]);
	shuffle(vec[0].begin(), vec[0].end(), gen);
	shuffle(vec[1].begin(), vec[1].end(), gen);
	vector<pair<long long, long long>> res;
	while (vec[0].size() > 1 || vec[1].size() > 1) {
		int o = gen() & 1;
		if (vec[o].size() < 2) o ^= 1;
		long long x = vec[o].back();
		vec[o].pop_back();
		long long y = vec[o].back();
		vec[o].pop_back();
		res.emplace_back(x, y);
		int oo = (x + y) / 2 & 1;
		vec[oo].push_back((x + y) / 2);
	}
	if (vec[0].size() + vec[1].size() == 1) {ans.swap(res); return 1;}
	return 0;
}

int main() {
	freopen("cow.in", "r", stdin);
	freopen("cow.out", "w", stdout);
	scanf("%d", &T);
	while (T--) {
		scanf("%d", &n);
		for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
		int flag = 0;
		for (int i = 1; i <= 400; i++)
			if (check()) {flag = 1; break;}
		if (!flag) {puts("-1"); continue;}
		for (auto i : ans) printf("%lld %lld\n", i.first, i.second);
	}
	return 0;
}

4.30

B TopCoder AmoebaDivOne

给一个 n×mn\times m 的 01 矩阵，求由 00 组成的凸多边形的个数，其中凸多边形的定义是：

  • 对于任意 (x1,y),(x2,y)(x_1, y), (x_2, y) 在其中则对于任意 x1≤k≤x2x_1 \le k \le x_2，(k,y)(k, y) 也在其中。
  • 对于任意 (x,y1),(x,y2)(x, y_1), (x, y_2) 在其中则对于任意 y1≤k≤y2y_1 \le k \le y_2，(x,k)(x, k) 也在其中。

等价于从上到下每行的区间左端点先单调不升再单调不降，右端点先单调不降再单调不升。

设 dpi,l,r,0/1,0/1dp_{i, l, r, 0 / 1, 0 / 1} 表示考虑到第 ii 行，当前行区间为 [l,r][l, r]，左端点在单调不升阶段 / 单调不降阶段，右端点在单调不降阶段 / 单调不升阶段，转移时左端点阶段变化必须上升，右端点阶段变化必须下降。

直接来 O(n5)O(n^5)，但是将 [l,r][l, r] 的值放到点 (l,r)(l, r) 上，每次转移过来都是一个子矩形，前缀和优化即可。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

const int mod = 1e9 + 7;

int n, m, a[105][105], dp[105][105][105][4], sum[105][105][105][4], ans;

int calc(int i, int l1, int l2, int r1, int r2, int s) {
	return ((long long)sum[i][l2][r2][s] +
		mod - sum[i][l1 - 1][r2][s] + mod - sum[i][l2][r1 - 1][s] + sum[i][l1 - 1][r1 - 1][s]) % mod;
}

int main() {
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) {
		string s;
		cin >> s;
		m = s.length() * 2;
		s = " " + s;
		for (int j = 1; j <= m / 2; j++) {
			int v;
			if (isdigit(s[j])) v = s[j] - '0';
			else v = s[j] - 'a' + 10;
			a[2 * i - 1][2 * j - 1] = v & 1;
			a[2 * i - 1][2 * j] = v >> 1 & 1;
			a[2 * i][2 * j - 1] = v >> 2 & 1;
			a[2 * i][2 * j] = v >> 3 & 1;
		}
	}
	n *= 2;
	// for (int i = 1; i <= n; i++, eputs(""))
	// 	for (int j = 1; j <= m; j++) eprintf("%d", a[i][j]);
	for (int i = 1; i <= n; i++) {
		for (int l = 1; l <= m; l++)
			for (int r = l; r <= m; r++)
				if (!a[i][r]) {
					dp[i][l][r][0] = 1;
					for (int s = 0; s < 4; s++)
						for (int t = s; ; t = (t - 1) & s) {
							int ll = l - ((s ^ t) & 1), rr = r + ((s ^ t) >> 1 & 1);
							int l1, l2, r1, r2;
							if (s & 1) l1 = 1, l2 = ll;
							else l1 = ll, l2 = r;
							if (s >> 1 & 1) r1 = rr, r2 = m;
							else r1 = l, r2 = rr;
							dp[i][l][r][s] = (dp[i][l][r][s] + calc(i - 1, l1, l2, r1, r2, t)) % mod;
							if (!t) break;
						}
				} else break;
		for (int l = 1; l <= m; l++)
			for (int r = 1; r <= m; r++)
				for (int s = 0; s < 4; s++) {
					ans = (ans + dp[i][l][r][s]) % mod;
					sum[i][l][r][s] =
						((long long)sum[i][l - 1][r][s] + sum[i][l][r - 1][s] +
						mod - sum[i][l - 1][r - 1][s] + dp[i][l][r][s]) % mod;
				}
	}
	// eprintf("%d\n", dp[2][1][1][0]);
	printf("%d\n", ans);
	return 0;
}

C

给你一个长度为 nn 的整数序列，每次询问 L,RL, R，求：

max⁡L≤l<r≤R1r−l∑i=lrai\max\limits_{L \le l < r \le R} \frac{1}{r - l}\sum\limits_{i = l}^r a_i

先二分答案变成全局减去某个数后最大子段和，在线段树每个节点维护所有子段的直线的下凸壳（可以对偶到点的上凸壳），建树 pushup 时闵可夫斯基和即可。然后询问就是 O(log⁡n)O(\log n) 个凸包上二分出来再最大子段和合并。因为是实数二分，所以需要记录答案对应的区间。

复杂度 O(nlog⁡3n)O(n \log^3 n)，跑不过 O(nnlog⁡n)O(n \sqrt{n} \log n)，甚至过不了/ll

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

namespace Geometry {
	struct Vect {
		long long x, y;
		int l, r;

		Vect() = default;
		Vect(long long _x, long long _y, int _l, int _r): x(_x), y(_y), l(_l), r(_r) {}
		Vect operator+(const Vect &a) const {return Vect(x + a.x, y + a.y, min(l, a.l), max(r, a.r));}
		Vect operator-(const Vect &a) const {return Vect(x - a.x, y - a.y, l, r);}
		long long operator*(const Vect &a) const {return x * a.x + y * a.y;}
		long long operator^(const Vect &a) const {return x * a.y - y * a.x;}
		Vect &operator+=(const Vect &a) {return *this = *this + a;}
		Vect &operator-=(const Vect &a) {return *this = *this - a;}
	};
	using Point = Vect;
	using Polygon = vector<Point>;

	inline Polygon Andrew(const Polygon &a) {
		Polygon ans;
		ans.reserve(a.size());
		ans.push_back(a[0]);
		for (int i = 1; i < (int)a.size(); i++) {
			while (ans.size() > 1) {
				Point tmp = ans.back();
				ans.pop_back();
				if (((tmp - ans.back()) ^ (a[i] - tmp)) < 0) {ans.push_back(tmp); break;}
			}
			ans.push_back(a[i]);
		}
		ans.shrink_to_fit();
		return ans;
	}
	inline Polygon Minkowski(const Polygon &l, const Polygon &r) {
		Polygon diffl, diffr;
		int sizl = l.size(), sizr = r.size();
		for (int i = 1; i < sizl; i++) diffl.push_back(l[i] - l[i - 1]);
		for (int i = 1; i < sizr; i++) diffr.push_back(r[i] - r[i - 1]);
		Polygon ans;
		ans.push_back(l[0] + r[0]);
		int pl = 0, pr = 0;
		while (pl < sizl - 1 && pr < sizr - 1)
			if ((diffl[pl] ^ diffr[pr]) < 0) ans.push_back(ans.back() + diffl[pl++]);
			else ans.push_back(ans.back() + diffr[pr++]);
		while (pl < sizl - 1) ans.push_back(ans.back() + diffl[pl++]);
		while (pr < sizr - 1) ans.push_back(ans.back() + diffr[pr++]);
		return ans;
	}
}
using namespace Geometry;

int n, q;
long long a[100005];
struct interval {
	double val;
	int l, r;

	interval() = default;
	interval(double _val, int _l, int _r): val(_val), l(_l), r(_r) {}
	interval operator+(const interval &x) const {return interval(val + x.val, min(l, x.l), max(r, x.r));}
	bool operator<(const interval &x) const {return val < x.val;}
};
struct node {
	interval lmx, rmx, ans, sum;

	node() = default;
	node(interval _lmx, interval _rmx, interval _ans, interval _sum):
		lmx(_lmx), rmx(_rmx), ans(_ans), sum(_sum) {}
	node operator+(const node &x) const {
		return node(
			max(lmx, sum + x.lmx),
			max(x.rmx, x.sum + rmx),
			max({ans, x.ans, rmx + x.lmx}),
			sum + x.sum
		);
	}
};
interval querymax(const Polygon &vec, double x) {
	if (vec.empty()) return interval(-1e18, 1, 0);
	interval ans = interval(vec.back().x * x + vec.back().y, vec.back().l, vec.back().r);
	if (vec.size() == 1) return ans;
	int l = 0, r = vec.size() - 2;
	while (l < r) {
		int mid = (l + r) / 2;
		if (vec[mid].x * x + vec[mid].y > vec[mid + 1].x * x + vec[mid + 1].y) r = mid;
		else l = mid + 1;
	}
	return max(ans, interval(vec[r].x * x + vec[r].y, vec[r].l, vec[r].r));
}
struct SegmentTree {
#define ls(x) (x * 2)
#define rs(x) (x * 2 + 1)

	Polygon lmx[400005], rmx[400005], ans[400005];
	long long sum[400005];
	int l[400005], r[400005];

	void build(int ll, int rr, int now = 1) {
		l[now] = ll, r[now] = rr;
		lmx[now].reserve(rr - ll + 1);
		rmx[now].reserve(rr - ll + 1);
		ans[now].reserve(rr - ll + 1);
		if (ll == rr) {
			lmx[now].emplace_back(1, a[ll], ll, rr);
			rmx[now].emplace_back(1, a[rr], ll, rr);
			sum[now] = a[ll];
			return ;
		}
		int mid = (ll + rr) / 2;
		build(ll, mid, ls(now)), build(mid + 1, rr, rs(now));
		lmx[now] = lmx[ls(now)];
		for (auto i : lmx[rs(now)])
			lmx[now].emplace_back(i.x + r[ls(now)] - l[ls(now)] + 1, i.y + sum[ls(now)], ll, i.r);
		inplace_merge(lmx[now].begin(), lmx[now].begin() + lmx[ls(now)].size(), lmx[now].end(),
			[](const Point &u, const Point &v) {
				return u.x != v.x ? u.x < v.x : u.y > v.y;
			}
		);
		lmx[now] = Andrew(lmx[now]);
		rmx[now] = rmx[rs(now)];
		for (auto i : rmx[ls(now)])
			rmx[now].emplace_back(i.x + r[rs(now)] - l[rs(now)] + 1, i.y + sum[rs(now)], i.l, rr);
		inplace_merge(rmx[now].begin(), rmx[now].begin() + rmx[rs(now)].size(), rmx[now].end(),
			[](const Point &u, const Point &v) {
				return u.x != v.x ? u.x < v.x : u.y > v.y;
			}
		);
		rmx[now] = Andrew(rmx[now]);
		ans[now] = Minkowski(rmx[ls(now)], lmx[rs(now)]);
		int top = ans[now].size();
		for (auto i : ans[ls(now)]) ans[now].push_back(i);
		inplace_merge(ans[now].begin(), ans[now].begin() + top, ans[now].end(),
			[](const Point &u, const Point &v) {
				return u.x != v.x ? u.x < v.x : u.y > v.y;
			}
		);
		top = ans[now].size();
		for (auto i : ans[rs(now)]) ans[now].push_back(i);
		inplace_merge(ans[now].begin(), ans[now].begin() + top, ans[now].end(),
			[](const Point &u, const Point &v) {
				return u.x != v.x ? u.x < v.x : u.y > v.y;
			}
		);
		ans[now] = Andrew(ans[now]);
		sum[now] = sum[ls(now)] + sum[rs(now)];
		return ;
	}
	node query(int ll, int rr, double x, int now = 1) {
		if (ll <= l[now] && r[now] <= rr) {
			// eprintf("%d %d\n", l[now], r[now]);
			node tmp = node(
				querymax(lmx[now], x),
				querymax(rmx[now], x),
				querymax(ans[now], x),
				interval(sum[now] + x * (r[now] - l[now] + 1), l[now], r[now])
			);
			// eprintf("%lf %lf %lf %lf\n", tmp.lmx.val, tmp.rmx.val, tmp.ans.val, tmp.sum.val);
			return tmp;
		}
		int mid = (l[now] + r[now]) / 2;
		node res;
		if (ll <= mid) res = query(ll, rr, x, ls(now));
		if (mid < rr) {
			if (ll <= mid) res = res + query(ll, rr, x, rs(now));
			else res = query(ll, rr, x, rs(now));
		}
		return res;
	}

#undef ls
#undef rs
} tr;

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> q;
	for (int i = 1; i <= n; i++) cin >> a[i];
	tr.build(1, n);
	// return 0;
	for (int i = 1; i <= n; i++) a[i] += a[i - 1];
	// eprintf("%.9lf\n", tr.query(2, 4, 0.953674).ans.val);
	// return 0;
	while (q--) {
		int l, r;
		cin >> l >> r;
		double le = -2000000, ri = 2000000;
		interval res;
		while (ri - le > 1e-3) {
			double mid = (le + ri) / 2;
			res = tr.query(l, r, -mid).ans;
			if (res.val + mid >= 0) le = mid;
			else ri = mid;
		}
		// eprintf("%Lf\n", le);
		interval tmp = res;
		// eprintf("%d %d\n", tmp.l, tmp.r);
		long long z = a[tmp.r] - a[tmp.l - 1], m = tmp.r - tmp.l;
		long long g = __gcd(z, m);
		z /= g, m /= g;
		if (m < 0) z = -z, m = -m;
		cout << z << '/' << m << '\n';
	}
	return 0;
}

5.1

D

若干根 1×m1\times m 的木条堆了 n+1n + 1 层塔，相邻两层木条互相垂直，每层大小为 m×mm\times m，告诉你每层哪些位置有木条，两个人轮流抽，每次抽一根，不能抽第 n+1n + 1 层，若抽完之后某层前 ⌈m2⌉\lceil\frac{m}{2}\rceil 个木条都没了或后 ⌈m2⌉\lceil\frac{m}{2}\rceil 个木条都没了那他就输了，求是否先手必胜。

视为一次移动合法当且仅当抽完后不输，就是公平组合游戏，对于每一层，设 l,rl, r 为前 / 后 ⌊m2⌋\lfloor\frac{m}{2}\rfloor 个里有几个，midmid 为中间那个，则当 mid=0mid = 0 时，sg(l,r,mid)=(l+r)(mod2)sg(l, r, mid) = (l + r) \pmod 2。

否则通过打表发现：

sg(l,r,1)={r(mod2)l=1l(mod2)r=11−(l+r)(mod2)otherwise.sg(l, r, 1) = \begin{cases} r \pmod 2 & l = 1 \\ l \pmod 2 & r = 1 \\ 1 - (l + r) \pmod 2 & \text{otherwise.} \end{cases}

然后就做完了。

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
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, m, ans;

int f(int n, int m) {
	if (!n) return m % 2;
	if (!m) return n % 2;
	if (n == 1) return 3 - m % 2;
	if (m == 1) return 3 - n % 2;
	return 1 - (n + m) % 2;
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		int l = 0, r = 0, mid = 0;
		for (int j = 1; j <= m; j++) {
			int x;
			scanf("%1d", &x);
			if (j <= (m + 1) / 2) l += x;
			if (j > m / 2) r += x;
			if (m % 2 && j == m / 2 + 1) mid += x;
		}
		l -= mid, r -= mid;
		if (!mid) ans ^= (l + r) % 2;
		else ans ^= f(l, r);
	}
	puts(ans ? "Alice" : "Bob");
	return 0;
}
/*
f[n][m] = mex(f[n - 1][m], f[n][m - 1], (n + m) % 2)
f[n][0] = f[0][n] = n % 2

4 3
111
101
110
010

2 ^ 0 ^ 1 ^ 0
*/

J

给一个自动机，求一个串使得泵长度小于状态集大小，要求串长不超过状态集大小的 33 倍。

也就是找一条起始状态到任意一个结束状态的路径使得他有环。

先缩点，然后记一下每个强连通分量有没有环，找一条合法的路径，接下来就是构造强连通分量内部的路径。

现在就是要在一个强连通分量中从 uu 走到 vv 并走一个环。
我的构造就是先从 uu 走到根，这个可以通过走树边和反祖 / 横叉边实现，需要注意跳到的点的 lowlow 必须是经过的所有点的 lowlow 的最小值，否则会在一个环上死循环。
然后在根上走一个环，显然直接找一个只有树边和一条反祖边的环就行。
最后从根走树边到 vv 就行了。

刚好每个点至多经过 33 次。

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
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
// 長い夜の終わりを信じながら
// Think twice, code once.
#include <queue>
#include <vector>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
#define eputchar(c) putc(c, stderr)
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#define eputs(str) fputs(str, stderr), putc('\n', stderr)
using namespace std;

int n, m, k, f[500005], intr[1000005];
struct dfa {
	int tot, hd[500005];
	int nxt[1000005], to[1000005], dt[1000005];

	void add(int u, int v, int c) {
		nxt[++tot] = hd[u];
		hd[u] = tot;
		to[tot] = v;
		dt[tot] = c;
		return ;
	}
} dfa;
struct graph {
	int tot, hd[500005];
	int nxt[1000005], to[1000005], ru[1000005], rc[1000005];

	void add(int u, int v, int _ru, int _rc) {
		nxt[++tot] = hd[u];
		hd[u] = tot;
		to[tot] = v;
		ru[tot] = _ru, rc[tot] = _rc;
		return ;
	}
} g;
int timer, dfn[500005], low[500005], scc_cnt, scc[500005], rt[500005], cnt[500005];
vector<int> stk;
int in[500005], pre[500005][2];
string ans;

void Tarjan(int now) {
	dfn[now] = low[now] = ++timer;
	stk.push_back(now);
	for (int i = dfa.hd[now]; i; i = dfa.nxt[i])
		if (!dfn[dfa.to[i]])
			Tarjan(dfa.to[i]), intr[i] = 1, low[now] = min(low[now], low[dfa.to[i]]);
		else if (!scc[dfa.to[i]]) low[now] = min(low[now], dfn[dfa.to[i]]);
	if (low[now] == dfn[now]) {
		rt[++scc_cnt] = now;
		for (int x = 0; x != now; stk.pop_back()) {
			x = stk.back();
			scc[x] = scc_cnt;
			cnt[scc_cnt]++;
		}
		for (int i = dfa.hd[now]; i; i = dfa.nxt[i])
			if (dfa.to[i] == now) {cnt[scc_cnt]++; break;}
	}
	return ;
}
int toroot(int now, int l, string &ans) {
	// eprintf("%d %d\n", now, l);
	if (now == rt[scc[now]]) return 1;
	for (int i = dfa.hd[now]; i; i = dfa.nxt[i])
		if (dfn[dfa.to[i]] > dfn[now]) {
			if (intr[i] && scc[dfa.to[i]] == scc[now])
				if (toroot(dfa.to[i], l, ans)) {ans.push_back(dfa.dt[i] + 'a'); return 1;}
		} else if (scc[dfa.to[i]] == scc[now] && dfn[dfa.to[i]] < l) {
			if (toroot(dfa.to[i], dfn[dfa.to[i]], ans)) {ans.push_back(dfa.dt[i] + 'a'); return 1;}
		}
	return 0;
}
int cycle(int now, string &ans) {
	for (int i = dfa.hd[now]; i; i = dfa.nxt[i])
		if (dfa.to[i] == rt[scc[now]]) {ans.push_back(dfa.dt[i] + 'a'); return 1;}
		else if (intr[i] && scc[dfa.to[i]] == scc[now])
			if (cycle(dfa.to[i], ans)) {ans.push_back(dfa.dt[i] + 'a'); return 1;}
	return 0;
}
int topoint(int now, int to, string &ans) {
	if (now == to) return 1;
	for (int i = dfa.hd[now]; i; i = dfa.nxt[i])
		if (intr[i] && scc[dfa.to[i]] == scc[now])
			if (topoint(dfa.to[i], to, ans)) {ans.push_back(dfa.dt[i] + 'a'); return 1;}
	return 0;
}
void getans(int u, int v) {
	// eprintf("%d %d\n", u, v);
	string tmp;
	toroot(u, dfn[u], tmp);
	reverse(tmp.begin(), tmp.end());
	ans += tmp;
	if (cnt[scc[u]] > 1) {
		string().swap(tmp);
		cycle(rt[scc[u]], tmp);
		reverse(tmp.begin(), tmp.end());
		ans += tmp;
		// cerr << tmp << '\n';
	}
	string().swap(tmp);
	// if (u == 1 && v == 2) eputs("?");
	topoint(rt[scc[u]], v, tmp);
	reverse(tmp.begin(), tmp.end());
	ans += tmp;
	return ;
}

int main() {
	// freopen("in.txt", "r", stdin);
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m >> k;
	for (int i = 1; i <= k; i++) {
		int x;
		cin >> x;
		f[x] = 1;
	}
	for (int i = 1; i <= m; i++) {
		int u, v;
		char c;
		cin >> u >> v >> c;
		dfa.add(u, v, c - 'a');
	}
	for (int i = 1; i <= n; i++)
		if (!dfn[i]) Tarjan(i);
	// for (int i = 1; i <= n; i++) eprintf("%d ", rt[i]);
	for (int i = 1; i <= n; i++)
		for (int j = dfa.hd[i]; j; j = dfa.nxt[j])
			if (scc[dfa.to[j]] != scc[i]) g.add(scc[i], scc[dfa.to[j]], i, j), in[scc[dfa.to[j]]]++;
	queue<int> q;
	for (int i = 1; i <= n; i++)
		if (!in[i]) q.push(i);
	while (!q.empty()) {
		int now = q.front();
		q.pop();
		if (scc[1] == now) pre[now][0] = -1, pre[now][1] = cnt[now] > 1 ? -1 : 0;
		for (int i = g.hd[now]; i; i = g.nxt[i]) {
			if (pre[now][0]) {
				pre[g.to[i]][0] = now;
				if (cnt[g.to[i]] > 1) pre[g.to[i]][1] = now;
			}
			if (pre[now][1]) pre[g.to[i]][1] = now;
			if (!--in[g.to[i]]) q.push(g.to[i]);
		}
	}
	int t = 0;
	for (int i = 1; i <= n; i++)
		if (f[i] && pre[scc[i]][1]) {t = i; break;}
	if (!t) {puts("-1"); return 0;}
	vector<int> vec;
	for (int i = scc[t]; i != -1; ) {
		vec.push_back(i);
		if (pre[i][1]) i = pre[i][1];
		else i = pre[i][0];
	}
	reverse(vec.begin(), vec.end());
	int now = 1;
	for (int i = 0; i < (int)vec.size() - 1; i++) {
		for (int j = g.hd[vec[i]]; j; j = g.nxt[j])
			if (g.to[j] == vec[i + 1]) {
				getans(now, g.ru[j]);
				ans.push_back(dfa.dt[g.rc[j]] + 'a');
				now = dfa.to[g.rc[j]];
				break;
			}
	}
	// eprintf("%d %d\n", now, t);
	getans(now, t);
	// return 0;
	cout << ans << '\n';
	return 0;
}
/*
7 9 1
3
1 2 a
2 5 c
5 2 d
5 7 b
5 3 a
4 2 b
2 3 a
3 3 e
3 6 a

*/
留言