总结

腊月初二。今天是模拟赛，还行，很有趣。D2 改完了，还有一道题。简单讲一讲，今天发挥还是没有完全发挥感觉，有一点兴致低落。D2T1 都想了好久，后面就没有太大动力了。需要改正。

题解

有两道题知道出处，其他两道不知道。

A. 按题目填色

原题：IOI 2016 Day2 Paint By Numbers 。

简要题意：给定一个长度小于等于的序列和一个不完整的 01 串，要求这个 01 串把黑色连通块长度按顺序搞下来之后和序列一样，让你求对于所有可能填法，如果一个位置固定 0 或 1 就输出这个数，不然输出问号。这个就正着反着 dp 一下然后验证一下就行。

B. 星际逃亡

有空间内个点，你要从到，然后每个点做匀速直线运动或静止，每一维初始坐标绝对值小于等于且是整数。，在每个点最多停留秒，每次可以在一瞬间在从当前点跳到另外一个点，跳不一定是整数秒。然后求跳的路径中最长距离的最小值。

考虑二分，然后会发现两个点如果会出现边，就一定是一个区间。然后维护这个时间各个点是否可以到达。如果中间到达了，那么就可以。否则就不行。所以维护每条边加和删除的时间，然后所有混在一起排序。对于 S 的限制，我们容易发现如果一个时间一个点有出度，那么可以来回横跳，就没有关系。只有单独的时候就有。所以加边的时候维护一下两个点是否存在就行。然后如果加边是一个点有另一个点没有，就 dfs/bfs 没有的点，这个时间来转移还不能到的点，访问过的边就直接删掉。然后删除边就减一下度数，把边删掉（如果还没删）。如果度数为 0 了，就记录一下现在的时间就行。

P.S. 不用删边那些的也能过，暴力枚举就行，如果想更好可以使用 bitset，用 vector 的话不会。

C. 博弈问题

找不到原题。

就是一个树，每个点一个权值，然后求每个子树，A 先选择其中一个点的权值，B 后选择另外一个点的权值，然后 A 想使得异或尽量大，B 想使得异或尽量小，求这个值。就是用 Trie，然后用类似线段树合并的方法就行。

D.[AGC022F] Checkers

这道原题。但是数据范围变成了。

为什么会有人模拟赛搬 AGC F 啊？

洛谷题解都看得不是很懂，nflsoj 上面的倒是很有趣。

知识点：元素合并有两种表示方式，一种是个点的二叉树，一种是就是普通的数，爹爹干掉合并上儿子，儿子的排列就是合并的顺序。

终于会做法了！

这里准备直接把他的题解 copy 过来，主要是他讲得太好了，令人动容，而且比我讲的好，未来还可以再看看，再想想。绝对不是因为我懒。

每次做这种 atc 风格 DP 都是生不如死……

先扯一些关系不大的东西。

我们知道个元素合并次可以用一棵个点的二叉树表示。每次合并都新建节点，并连向两个集合的树的根，得到一棵新树。这样可以描述每次合并的两个集合的无序对的集合，但并不能知道合并的顺序（也不会有题目需要知道顺序），但起码需要符合这棵树的拓扑序。如果 A 合并到 B、B 合并到 A 不同（可以理解为 PK 的胜负，负者淘汰），那么此时这种方法并不能记录每次的输赢，但只需要把胜者放在左儿子、负者放在右儿子即可。

但还有另一种我以前不知道的描述合并关系的方法。这种方法重在描述每次合并的胜负，每次合并设 A 胜 B 负，则令 B 目前的胜者直接指向 A 目前的胜者。这样也可以得到一棵（内向）树，只不过恰有个节点，且是多叉树（相当于把二叉树的左儿子缩上去）。但普通情况并不能描述每次合并的两个集合的无序对的集合，然而依然可以稍作改进做到。对于某个节点，记其儿子序列为，则必然恰好存在一个排列，使得参与的合并是与合并的，那就将儿子序列按照这个排列排序即可。这种方法依然不能知道合并顺序，但可以肯定合并是按照树的拓扑序进行的。所以这和二叉树方法是等价的。

开始讲这个题。可以认为一开始是个向量，使得。每次PK 是合并为或。注意到，这里涉及胜负，而多叉树描述法擅长描述这个。我之前只知道二叉树描述法，推了半天毫无头绪/yun

考虑其多叉树。每次胜者的集合里所有对最终向量的第分量贡献了的系数，负者贡献。设第分量为，尝试将在树上表示出来。显然就是的深度。而比较复杂，好在我们只关心其奇偶性。

在往上爬的过程中，每爬一次看它在当前节点的儿子序列中排第个，则说明所在集合胜了次（这里排列 与之前的描述是相反的/cy），对有的贡献。而它胜儿子们还有额外的贡献，其中是的儿子树。这样的表达太难受了，考虑写一个用父亲的值表达的递推式。容易写出，其中往上爬一次的。如果再将的含义 reverse 一次，表达式则简单很多，为（当然是模意义下的）。

又注意到：设最终能得到某一个向量，其元素的可重集为，则任意可重集为的向量都能达到（只要置换一下元素的地位即可）。这意味着我们可以从可重集的角度出发去计数，但要乘上，这要求我们的 DP 是以一种一种的为阶段的。

下面正式开始 DP。设为有个节点、至多层的所有多叉树的所有可能的可重集的可重集排列数之和。由于以层为阶段，每层的相等，只有两种可能的，极易做到转移时立刻决定并以其为系数。再仔细想想，其实根本不需要记录，直接当作在考虑目前这棵树的最后一层即可，毕竟各层无本质区别（第一层除外，必须恰有一个点，所以要特判）。

考虑枚举最后一层的的个数，以及的个数。考察递推式，最后一层值为，所以仅考虑和。那么对于倒数第二层的某个节点，如果是偶数，则它的儿子们的固定，却有一半是一半是，所以儿子们的值一定是一半一半。一直这样下去的话必有，需要为奇数来调节。类似推理，可以知道这样的儿子们中的会比的多一个。

于是一种方案就是倒数第二层有个为奇数的，且这些的值都要等于，偶数点无所谓，但要保证奇偶总共至少有一个节点。只要是存在对应多叉树满足这个条件的向量元素可重集，便可将个、个接在下面，于是直接转移到对应状态即可。但是有那么一种可能，就是倒数第二层为奇数的的个数还可以是大于且与之奇偶性相同的数，并且的比的多个。把这些情况的 DP 值都加在一起吗？对不起，可能有重复。一种理想情况是，存在某一种状态的所有可能可重集完全包含其它状态，那就可以只算这个状态。幸运的是，可以证明个奇数的状态就是完全包含其它的。因为若超过，则必存在两个奇数点的值不同，则将其中一个的儿子给另一个，该层值可重集不变，且奇数点减少了两个。

好的，现在将 DP 定义扩展至表示个数，最后一层，且这个的值必须都等于。重新考虑转移，可以发现相比于之前多了的影响，之前都是的。那么设 $c’u=c_u-s_ux,ys_uc’=0/1j,kx’,y’c’=0/1x’’,y’’c=0/1\frac{1}{x’’!y’’!}dp{i-j-x-y,\lvert x’-y’ \rvert,[x’>y’]}$。

这样时间复杂度是，可以过 agc 原题，但过不了模拟赛（魔鬼笑）。

先放个四方代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

constexpr int N = 510;

int n;
int iv[N], fc[N], ifc[N];
int dp[N][N][2];

void mian() {
	n = read(), P = read();
	iv[1] = 1; REP(i, 2, n) iv[i] = (ll)iv[P % i] * (P - P / i) % P;
	fc[0] = ifc[0] = 1; REP(i, 1, n) fc[i] = (ll)fc[i - 1] * i % P, ifc[i] = (ll)ifc[i - 1] * iv[i] % P;
	dp[1][0][0] = dp[1][0][1] = dp[1][1][1] = 1;
	REP(i, 2, n) REP(j, 0, i - 1) REP(k, 0, 1) {
		REP(x, 0, i - 1 - j) REP(y, 0, i - 1 - j - x) if(j || x || y) {
			int x0 = x + (k == 1) * j, y0 = y + (k == 0) * j;
			int x00 = x + (k == 0) * j, y00 = y + (k == 1) * j;
			int ad = x0 < y0 ? dp[i - j - x - y][y0 - x0][0] : dp[i - j - x - y][x0 - y0][1];
			addto(dp[i][j][k], (ll)ifc[x00] * ifc[y00] % P * ad % P);
		}
	}
	int ans = dp[n][0][0];
	ans = (ll)fc[n] * ans % P;
	prt(ans), pc('\n');
}

考虑优化到。

观察代码，枚举，考虑分成四元组和来查看。

总贡献为（这里虽然不在求和枚举里，但也是被枚举的变量）。如果能知道后面这个的值，便达到了三方。注意到该仅与 j || x、、x + (k ? j : -j)、有关，其中 j || x 是 bool 值其复杂度可以忽略。这样还是涉及三个的量，有种的值（flag），计算每种的话加上枚举还是四方的复杂度。

但是注意到最后一项，如果就不需要记录了，那么就只有种，对每种暴力计算复杂度就是三方了。那呢？很简单，交换地位即可。

略微卡常，用了 18 次乘法取一次模的优化才过/qd

code:

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

constexpr int N = 510;

int n;
int iv[N], fc[N], ifc[N];
int dp[N][N][2];
ull f[N][3 * N][2][2];
int vis[N][3 * N][2];

void mian() {
	n = read();
	iv[1] = 1; REP(i, 2, n) iv[i] = (ll)iv[P % i] * (P - P / i) % P;
	fc[0] = ifc[0] = 1; REP(i, 1, n) fc[i] = (ll)fc[i - 1] * i % P, ifc[i] = (ll)ifc[i - 1] * iv[i] % P;
	dp[1][0][0] = dp[1][0][1] = dp[1][1][1] = 1;
	memset(f, -1, sizeof(f));
	REP(i, 2, n) REP(j, 0, i - 1) REP(k, 0, 1) { // 这优化，多是一件美逝啊…… 
		if(k == 0) {
			REP(x, 0, i - 1 - j) {
				ull &F = f[i - j - x][x + (k ? j : -j) + n][k][j || x];
				if(!~F) {
					F = 0; int c = 0;
					REP(y, 0, i - 1 - j - x) if(j || x || y) {
						int x0 = x + (k == 1) * j, y0 = y + (k == 0) * j;
						int y00 = y + (k == 1) * j;
						int ad = x0 < y0 ? dp[i - j - x - y][y0 - x0][0] : dp[i - j - x - y][x0 - y0][1];
						F += (ll)ifc[y00] * ad;
						if(++c == 18) F %= P, c = 0;
					} F %= P;
				}
				int x00 = x + (k == 0) * j;
				addto(dp[i][j][k], ifc[x00] * F % P);
			}
		} else {
			REP(y, 0, i - 1 - j) {
				ull &F = f[i - j - y][y + (!k ? j : -j) + n][k][j || y];
				if(!~F) {
					F = 0; int c = 0;
					REP(x, 0, i - 1 - j - y) if(j || x || y) {
						int x0 = x + (k == 1) * j, y0 = y + (k == 0) * j;
						int x00 = x + (k == 0) * j;
						int ad = x0 < y0 ? dp[i - j - x - y][y0 - x0][0] : dp[i - j - x - y][x0 - y0][1];
						F += (ll)ifc[x00] * ad;
						if(++c == 18) F %= P, c = 0;
					} F %= P;
				}
				int y00 = y + (k == 1) * j;
				addto(dp[i][j][k], ifc[y00] * F % P);
			}
		}
	}
	int ans = dp[n][0][0];
	ans = (ll)fc[n] * ans % P;
	prt(ans), pc('\n');
}

感谢 chenxia25 的题解 。

后记

感觉之前的总结都比较水。今天曾总通过现实反例让我意识到总结不能像记流水账一样。要有自己的看法和反思。