P11746 Dynamic Color Problem

Kingna · 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。