P3631 [APIO2011]方格染色

P3631 [APIO2011]方格染色

考虑如何刻画题意。发现对于任意一个 $n\times m$ 的矩形，所有 $2\times 2$ 的矩形异或和为 $(n-1)(m-1)\mathrm{\&}1$ ，而等价于四个角的值的异或值。对于确定位置 $(x,y)=k$ ，则有 $w_{1,1}\oplus w_{x,1}\oplus w_{1,y}\oplus k=(x-1)(y-1)\mathrm{\&}1$ 。考虑钦定 $w_{1,1}$ ，那么每次可以得到 $w_{x,1}$ 和 $w_{1,y}$ 的关系，这个异或关系的维护可以用并查集。

考虑方案数，一旦第一行和第一列确定了，矩阵剩下的一定都可以确定了，所有可行的方案都和一种行列对应。并查集合并后，除去 $w_{1,1}$ ，一个连通块有两个状态，故答案为 $2^{t-1}$ 。

注意特殊处理第一行第一列。

查看代码

#include <cstdio>
using namespace std;
template <class Type>
void read(Type &x)
{
    char c;
    while ((c = getchar()) < '0' || c > '9');
    x = c - '0';
    while ((c = getchar()) >= '0' && c <= '9')
        x = (x << 3) + (x << 1) + c - '0';
}
template <class Type, class ...rest>
void read(Type &x, rest &...y) { read(x), read(y...); }
template <class Type>
void write(Type x)
{
    if (x < 0) putchar('-'), x = ~x + 1;
    if (x > 9) write(x / 10);
    putchar(x % 10 + '0');
}
typedef long long LL;
const int N = 1e5 + 10, mod = 1e9;
int binpow (int b, int k)
{
    int res = 1;
    for (; k; b = (LL)b * b % mod, k >>= 1)
        if (k & 1) res = (LL)res * b % mod;
    return res;
}
bool d[N << 1];
int n, m, q, p[N << 1];
int fa (int x)
{
    if (p[x] == x) return x;
    int t = p[x];
    p[x] = fa(p[x]);
    d[x] ^= d[t];
    return p[x];
}
struct OP { int x, y; bool v; } o[N];
int calc (bool v)
{
    for (int i = 1; i < n + m; ++i)
        p[i] = i, d[i] = 0;
    for (int i = 1; i <= q; ++i)
    {
        int a = o[i].x, b = o[i].y == 1 ? 1 : o[i].y + n - 1;
        if (a == 1 && b == 1) continue;
        int x = fa(a), y = fa(b);
        if (x == y) { if (d[a] ^ d[b] ^ v ^ o[i].v) return 0; }
        else p[x] = y, d[x] ^= o[i].v ^ v ^ d[a] ^ d[b];
    }
    int res = 0;
    for (int i = 1; i < n + m; ++i) res += fa(i) == i;
    return binpow(2, res - 1);
}
int main ()
{
    read(n, m, q);
    int flag = -1;
    for (int i = 1; i <= q; ++i)
    {
        read(o[i].x, o[i].y, o[i].v);
        o[i].v ^= (o[i].x | o[i].y) & 1;
        if (o[i].x == 1 && o[i].y == 1) flag = o[i].v;
    }
    write(~flag ? calc(flag) : (calc(0) + calc(1)) % mod);
    return 0;
}