AT_arc089_d [ARC089F] ColoringBalls 笔记

模拟赛 #47 T4，超绝计数题，拼尽全力无法战胜。

由于不同的操作方式可能导致相同的结果，所以我们不能直接通过操作方式来计数，由于可以放弃操作，因此考虑如何用最简单的方式来操作得到一个序列。

首先，相邻的同色小球我们肯定是在一次涂色中解决，因此我们将相邻同色的部分缩成一个数，现在变成了形如 $R B R B WW R$ 一类的东西。

对于 $R$ ，显然只需要一个 $r$ 就能涂上了，考虑 $R B$ 交替的，显然我们可以只用一个 $r$ 「上底色」，然后下一步必定选 $b$ ，后面就任意涂了（因为涂 $r$ 可以视作 $B \to BRB$ ，涂 $b$ 反之），因此涂 $c_{i}$ 个 $B$ 的代价就是 $c_{i} + 1$ 。

因此枚举有 $x$ 个连续段是交替涂色，有 $y$ 个连续段只有 $R$ ，判定是否合法的时候，贪心地选前 $x$ 个 $r...b$ 给 $x$ 个连续段涂色，再在前面选 $y$ 个 $r$ 给 $y$ 个连续段涂色，称这个选择为「分配」。现在假设 $x$ 个连续段 $b$ 的个数分别是 $c_{1 \dots x}$ ，其中第 $i$ 个连续段合法的条件是「给 $i$ 分配的 $B$ 后面的还没被分配的数量（设这个数量是 ${sb}_{i}$ ） $\geq \sum_{j \in [i, x]} (c_{j} - 1)$ 」，这启示贪心地将 $c_{i}$ 大的分配给前面的连续段，也就是令 $c$ 降序排序。

于是考虑 DP，设 $f_{i, j, k}$ 表示考虑连续段 $[i, x]$ ， $j = \sum_{j^{'} \in [i, x]} (c_{j^{'}} - 1)$ ， $c_{i} = k$ ，并且考虑了连续段间内部排序方式的方案数，每次转移一次性决定所有 $c_{i} = k$ 的方案。

f_{i, j, k} \leftarrow \sum_{i + p \leq x + 1 \land 0 \leq j - p (k - 1) \leq {sb}_{i + p}} \sum_{l < k} (\binom{x - i + 1}{p}) f_{i + p, j - p (k - 1), l}

对于 $l$ ，使用前缀和优化，第一二维的转移是 $\ln n$ 的，因此状态数 $O (n^{3})$ ，转移 $O (\ln n)$ ，时间复杂度 $O (n^{3} \ln n)$ 。

接着考虑把这个方案还原到原本的 $n$ 个球有多少种情况。

首先，将 $x$ 种混色和 $y$ 种同色情况重排： $(\binom{x + y}{x})$ 。

对于具体的还原到 $n$ 个球，考虑使用插板法，弄出若干个盒子，每个盒子只能放同色的球，那么对于 $x$ 种的，有 $\dots - - - \dots$ 的情况（其中 $\dots$ 表示这个盒子不一定要放球），推到一下这里如何由 $f_{1, j, k}$ 得到必须放球的盒子数 $\sum (2 c_{i} - 1)$ ：

\sum (2 c_{i} - 1) = \sum (c_{i} - 1) + \sum c_{i} = 2 j + x

不一定要放球的盒子数就是 $2 x$ 。

同时，有 $y$ 个盒子放红色球，那么剩下中间的盒子都是必须放白色球，这里的个数是 $x + y - 1$ ，序列的两端不一定要放，这里的个数是 $2$ 。

因此必须放球的盒子个数 $A = 2 j + x + y + x + y - 1$ 。

不一定放球的盒子个数 $B = 2 x + 2$ 。

使用插板法变式可以得到 $(\binom{n + B - 1}{A + B - 1})$ 。

总结一下：

ans = \sum_{x = 0}^{n} \sum_{y = 0 \land (x \neq 0 \lor y \neq 0)}^{x - n} \sum_{j = 0}^{{sb}_{1}} \sum_{k = 0}^{n} (\binom{n + B - 1}{A + B - 1}) \times f_{1, j, k}

时间复杂度 $O (n^{5} \ln n)$ 但非常跑不满，空间复杂度 $O (n^{3})$ 。

AT_arc089_d [ARC089F] ColoringBalls 笔记 ​

AT_arc089_d [ARC089F] ColoringBalls 笔记