犀牛坦克：题解¶

解法比较¶

出题人解法逐行 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\) 下进行，减法结果规范到非负余数。