自动搬运

查看原文

来自洛谷，原作者为

	Kingna We live and die in the shadows for those we hold close and for those we never meet.

搬运于2025-08-24 23:09:55，当前版本为作者最后更新于2025-02-14 22:33:53，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

Subtask 1

可以直接 $2^{nm}$ 暴力求解，实现的好的话其实可以拿 $30$ 分。

Subtask 3~4

留给一些奇怪的做法。但其实没有人刻意去拿这档分。

Subtask 5

可以发现你获得的分数和 AI 获得的分数相加等于 $n+m$。则 $n+m$ 为偶数时，一定不存在合法解。又因为当 $n+m$ 为奇数时，若你获得的分数是偶数，那么 AI 一定是奇数，反之亦然。故两者一一对应，只需要求出其中一种方案数就是答案。

一整行或一整列颜色不完全相同的情况难以处理，所以考虑处理一整行或一整列颜色完全相同的情况。即现在需要解决这个问题：一整行或一整列颜色完全相同的数量是偶数的方案数。再反过来，先考虑为奇数的方案，再用总方案去减。

根据惯用做法，直接容斥/二项式反演。先考虑容斥系数的求解：对于答案至少有 $i$ 个产生贡献的情况，恰好是 $i$ 是最后一次计算。

• 当答案至少有 $0$ 个产生贡献时：容斥系数为 $0$。
• 当答案至少有 $1$ 个产生贡献时：之前产生 $\binom{1}{0}\times 0=0$ 的贡献，所以此时容斥系数为 $1$。
• 当答案至少有 $2$ 个产生贡献时：之前产生 $\binom{2}{0}\times 0+\binom{2}{1}\times 1=2$ 的贡献，所以此时容斥系数为 $-2$。
• 当答案至少有 $3$ 个产生贡献时：之前产生 $\binom{3}{0}\times 0+\binom{3}{1}\times 1+\binom{3}{2}\times -2=-3$ 的贡献，所以此时容斥系数为 $4$。
• 当答案至少有 $4$ 个产生贡献时：之前产生 $\binom{4}{0}\times 0+\binom{4}{1}\times 1+\binom{4}{2}\times -2+\binom{4}{3}\times 4=8$ 的贡献，所以此时容斥系数为 $-8$。

因此可以得到答案至少为 $x$ 时，容斥系数为 $(-2)^{x-1}$。

接下来计算答案：

• 只有行产生贡献：$\sum_{i=1}^n (-2)^{i-1}\binom{n}{i}2^i2^{(n-i)m}$。具体含义为从 $n$ 行中选择 $i$ 列颜色相同，他们颜色方案数为 $2^i$。其余位置方案数为 $2^{(n-i)m}$。
• 只有列产生贡献：$\sum_{i=1}^m (-2)^{i-1}\binom{m}{i}2^i2^{(m-i)n}$。同理可得。
• 都产生贡献：枚举行列分别产生 $i$ 和 $j$ 的贡献：$\sum_{i=1}^n\sum_{j=1}^m (-2)^{i+j-1}\binom{n}{i}\binom{m}{j}2\times 2^{(m-j)(n-i)}$​。如果列的颜色相同，行的颜色也相同，那么总的颜色只有全黑和全白两种。

复杂度 $\mathcal O(nm)$。期望得分 $56$ 分。

Subtask 6

考虑 $100$ 分的算法：

优化上面部分的第三个式子：

$$\begin{align*} f(n,m) &= \sum_{i=1}^n\sum_{j=1}^m (-2)^{i+j - 1}\binom{n}{i}\binom{m}{j}2\times 2^{(m - j)(n - i)} \\ &= \sum_{i=1}^n2 (-2)^{i - 1}\binom{n}{i}\sum_{j=1}^m (-2)^{j}\binom{m}{j}2^{(m - j)(n - i)} \\ &= \sum_{i=1}^n2 (-2)^{i - 1}\binom{n}{i}\sum_{j=1}^m \binom{m}{j}(-2)^{j}(2^{n - i})^{m - j} \\ &= \sum_{i=1}^n2 (-2)^{i - 1}\binom{n}{i} [(-2 + 2^{n - i})^m - 2^{(n - i)m}] \ \end{align*} $$

因此复杂度可以做到 $O(T(n+m)\log n)$。可以预处理二的次幂来减小常数，但是始终需要快速幂。期望得分 $100$。