题解 - AGC064D Red and Blue Chips

写这篇单纯是因为我读到的这题题解没有一篇讲的是俺听得懂的话（捂脸）。感觉是独立很难做的题目。

简述题意

有 $n$ 个只含 RB 的字符串 $S_i$，一开始每个字符串长度均为 $1$，保证 $S_n$ 是 B。对 $i$ 从 $1$ 到 $n-1$ 依次做如下操作：选择一个 $j$ 满足 $i<j\le n$ 且 $S_j$ 末字符为 B，然后将 $S_i$ 拼接到 $S_j$ 前面。问可以生成的 $S_n$ 个数 $\bmod\ 998244353$。$2\le n\le 300$。

分析

令输入的串为 $S$，生成的串为 $T$，经典的想法是为 $T$ 设计一个判定算法。

显然 $T_n$ 是 B。从 $S_1$ 到 $S_{n-1}$ 考虑会感觉每一位都没有一个位置，不如从 $S_{n-1}$ 到 $S_1$，依次考虑填入 $T$。

发现 $S_n$ 之前的一串极长的 R 必然成为 $T$ 的一个前缀，因为它们是最后放到 $S_n$ 开头的。然后将会扫到一个 B，假设它是 $S_b$，它会填到上述 R 前缀的后面、$T_n$ 的前面的某个位置。接下来扫到的一串极长的 R，在原来的过程中只有两种选择：放到 $S_b$ 前面或放到 $S_n$ 前面。如果选择的是放到 $S_n$ 前面，那么应该恰好在移动后的 $S_b$ 后面，因为它恰好在 $S_b$ 缀到 $S_n$ 前缀过去，$T$ 形如：

RRRRR....BRRRR.............B

如果选择的是放到 $S_b$ 的最前面，那应该是紧跟在上一次 R 的后面，而要在其它缀到 $S_b$ 前面的串之前，$T$ 形如：

RRR RRRR........B..........B

再下一个 B（以下为区分标为 b），可以填到两个空段的某一处，如：

RRRRR....b...BRRRRR....b...B

再然后的 R，类比上述推演可知，必然在以下之一：

• b 前面空段的最前；
• 紧随 b 之后；
• 剩下那个空段的最前，表示和 b 的去向不同。

归纳一下，相当于是 B 会插到某个位置，然后 R 可以插到最前，也可以紧随任意除了 $S_n$ 以外的 B 之后。就像是，每插入一个 B，就会把 $T$ 中它后面的一段连续的 R 给启用，表示可以往里面填 R。如果不能填 R 就是方案不合法。

这样的判定还不是 DFA，不够确定。考虑填 B，肯定希望接下来能容纳 R 的能力尽量强，所以除了第一段 R 被动地启用，后面都肯定会挑 $T$ 中一段最长的 R 来启用。

那就可以进一步形式化：假设 $S$ 中 B 有 $m$ 个，从右往左第 $i+1$ 个 B 右边的 R 有 $s_i$ 个，并令 $s_m=n-m$；假设把 $T$ 中除了第一段 R 以外的 R 段从长到短排序，令其长度前缀和为 $t_i$。则判定条件为：$\forall 1\le i\le m,t_i\ge s_i$。

把所有合法的 $t_1$ 都启用，后面的从长到短往里面填，最后要乘上多重集排列，转移有一个阶乘逆的系数，这是显然的分组背包，不讲了。复杂度看起来是 $O(n^3\log n)$，但是不太知道官方题解怎么能分析到 $O(n^3)$，可能是写法不太一样。

代码

你都会了，还要代码干嘛，套路卷积而已。

思考

这个题的性质太深奥了。上述理解有点暴力，但还是可以做出题的。其他题解有提到树形结构，也许可以帮助你获得更好的直觉，只是我还没悟到/ll。