codeforces 2092E 题解

前言

邀请赛前开始刷刷2100的题。这道题没有涉及到什么算法，但是思维含量很大，我是看到题解之后才注意到做法的。

题意

有一个n*m大小的地图，有k个点被染为白色或黑色，其余点没有被染色，求有多少种染色方案能够将其余所有点都染色，并且板上相邻单元格颜色不同的对数是偶数。

思路

Hint:

对于最终的结果，我们只关心相邻单元格颜色不同的对数的奇偶，而并不关心整个值。对某个单元格进行考虑，如果其相邻单元格数量为偶数，那么不管其为什么颜色，其对结果奇偶性没有影响

根据上面的思路，我们可以将所有的单元格分为三类：

角单元格，每个单元格有两个相邻的单元格
边单元格，每个单元格有三个相邻的单元格
中心单元格，每个单元格有四个相邻的单元格

显然角单元格和中心单元格的颜色对最终结果无影响。

为了简化问题，我们可以将所有中心单元格设置为白色，即使某些点已经确定为黑色，把他当作白色看不会影响结果。

其次，所有的边和角可以构成一个环，先考虑这个环内部对答案的贡献，可以发现相邻单元格颜色不同的对数总是偶数。

剩余我们需要考虑的就只剩下边单元格和中心单元格之间的互相影响。由于所有中心单元格均为白色，只有黑色的单元格可以产生一个贡献，也就是说黑色边单元格数量的奇偶决定了答案的奇偶。

接下来对边单元格能否构造出偶数个单元格进行分类：

所有边单元格都在开始被染过色，那么这其中黑色单元格的数量是确定的，若为奇数，则输出0，否则输出（2^(n*m-k)）（因为所有的未染色单元格都可以任意染色）
边单元格中存在未染色单元格，假设总共存在z个(z >= 1)，我们可以自由的染色其中的(z - 1)个单元格，而剩下的一个边单元格根据黑色单元格数量决定，总共的方案数应该为(2^(n*m-k-1))

接下来就很好做了。在读入初始染色格时对边单元格的黑白数量进行记录，之后分类讨论即可。

注意long long等细节

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

const int MOD = 1e9 + 7;
ll n, m, k;
ll cnt[2];

ll qpow(ll a, ll b) {
    assert(b >= 0);
    ll res = 1;
    while(b) {
        if(b & 1) res = res * a % MOD;
        a = a * a % MOD;
        b >>= 1;
    }
    return res;
}

void solve() {
    cin >> n >> m >> k;
    cnt[0] = cnt[1] = 0;
    for(int x, y, c, i = 1; i <= k; ++i) {
        cin >> x >> y >> c;
        bool flag1 = (x == 1 || x == n);
        bool flag2 = (y == 1 || y == m);

        if(flag1 ^ flag2) {
            cnt[c]++;
        }
    }

    if(cnt[0] + cnt[1] == 2 * (m + n) - 8) {
        if(cnt[0] & 1) cout << 0 << endl;
        else cout << qpow(2, n * m - k) << endl;  
    } else {
        cout << qpow(2, n * m - k - 1) << endl;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int t;  cin >> t;
    while(t--) {
        solve();
    }

    return 0;
}

后记

今天cf挂掉了，题目交了好久后才告诉我超时。我一开始使用int类型存储所有数据，在取模之前使用* 1ll转化为long long类型数，但是可能某个地方忘记加写暴了（可以注意到我在快速幂中加了断言，提交答案时确实出现了几发RE），最后全改成ll就好了。

其实这道题的重点还是在思维上。对网格图进行的每一步处理思维量都很大（看数据范围前我的思路是dp，但是看到1e9的数据范围胆怯了）