# 犀牛坦克：题解

## 解法比较

出题人解法逐行 DP，每列状态为“到目前始终同色，颜色为 $c$”或“已经出现不同颜色”。加入一行时，枚举仍同色的列中哪些在这一行变为不同色：保持者取对应颜色概率，改变者取其余颜色概率之和，已经不同色者不受限制；再减去与这些条件相容的整行单色情况。新状态清除所有已改变列的颜色。列一旦不同色便不能恢复，因此这些转移互斥且完整，最后取所有列均已不同色的状态。

设边长为 $n$ 、颜色数为 $m$ .抽象状态有 $(m+1)^n$ 个，每状态至多 $2^n$ 次转移，每次 $O(n+m)$ ，故 DP 时间上界为 $O(n(n+m)2^n(m+1)^n)$ .出题人实现每列固定占三位，还扫描和存储 $8^n$ 个编码，增加 $O(n8^n)$ 扫描时间、占 $O(8^n+n^2m)$ 空间。Codex（GPT-6）采用的实现直接对单色列做容斥，枚举时间为 $O(n^2(m+1)^n)$ ，空间为 $O(n^2m)$ ；两者均需进行概率归一化预处理。收益是消除逐状态的子集转移和指数数组，代价是改用带正负号的容斥计算。

## 对单色列容斥

将元素全相同的行或列称为单色。先保证每一行非单色，再对单色列做容斥。每列选择“不作限制”或“强制全为颜色 $c$”，共有 $(m+1)^n$ 个选择。

设受限列集合为 $S$ ，列 $j$ 的指定颜色为 $c_j$ .该项符号为 $(-1)^{\lvert S\rvert}$ .在列限制固定后，各行涉及独立的位置，故满足列限制且所有行非单色的概率为各行相应概率的乘积。

## 一行的概率

预处理 $R_{i,c}=\prod_{j=1}^{n}p_{i,j,c}$ ，表示第 $i$ 行全为颜色 $c$ 的概率。令

$$Q_i=\prod_{j\in S}p_{i,j,c_j}$$

空乘积为 $1$ .第 $i$ 行满足列限制且非单色的概率 $G_i$ 分三种情况：

- $S$ 为空：$G_i=1-\sum_c R_{i,c}$ .
- 受限列全部指定同一颜色 $c$ ：$G_i=Q_i-R_{i,c}$ .
- 受限列指定了至少两种颜色：该行已经不可能单色，$G_i=Q_i$ .

最后答案为

$$\sum_{S,\,(c_j)_{j\in S}}(-1)^{\lvert S\rvert}\prod_{i=1}^{n}G_i$$

## 正确性

对每列的单色事件应用容斥。某列全为不同颜色的事件互斥，因此选中该列后，可以对指定颜色的概率直接求和。上述枚举恰好列出这些交集。每一行通过扣除与列限制相容的全部单色情况，准确计算该交集下的非单色概率；独立性允许各行相乘。因此容斥结果正是所有行列均非单色的概率。

## 复杂度与实现

每个列选择状态用 $O(n^2)$ 时间计算各行贡献，枚举部分为 $O(n^2(m+1)^n)$ .用快速幂求每个位置权重和的逆元，预处理为 $O(n^2(m+\log P))$ .总空间为 $O(n^2m)$ .所有运算在模 $P$ 下进行，减法结果规范到非负余数。