BZOJ 2303 - [Apio2011]方格染色

Published on 2016-04-29

题目地址

描述

Sam和他的妹妹Sara有一个包含 n×mn \times m 个方格的表格。她们想要将其的每个方格都染成红色或蓝色。
出于个人喜好,他们想要表格中每个 2×22 \times 2 的方形区域都包含奇数个(1 个或 3 个)红色方格。例如,右图是一个合法的表格染色方案(在打印稿中,深色代表蓝色,浅色代表红色) 。
可是昨天晚上,有人已经给表格中的一些方格染上了颜色!现在Sam和Sara非常生气。不过,他们想要知道是否可能给剩下的方格染上颜色,使得整个表格仍然满足她们的要求。如果可能的话,满足他们要求的染色方案数有多少呢?

分析

我希望描述的尽量清晰,不跳跃。
设行数为 nn,列数为 mm 如果没有限制,那么合法的方案数为:

2m2n12^m * 2^{n - 1}

其中 2m2^m 是第一行能够染色的总方案数,2n12^{n - 1} 对应在上一行确定的情况下,这一行总是有 2 种可行方案,除去第 1 行,一共有 n1n - 1 行都有两种方案,故为 2n12^{n - 1}
两种方案?

  1. 上一行奇数列不变,偶数列取反。
  2. 上一行偶数列不变,奇数列取反。

我们只对 (1)(1) 证明,(2)(2) 是类似的。我们截取两列来看,不妨设左边为奇数列,如果使用方案一的话,看起来是这样的。

xyx1y\begin{matrix} x & y \\x & 1 - y\end{matrix}

那么这个 2×22 \times 2 的方形区域的和为 2x+1,x{0,1}2x + 1,x \in \{0, 1\},必定取到 {1,3}\{1, 3\}。若左边为偶数列,证明类似。
所以每一行在上一行确定的情况下,有 2 种可行方案。

现在考虑已经有一些格子被涂上色的情况,我们不妨在最上面加一行,不难得到,加一行的答案是不加一行的两倍,所以我们计算加一行的答案即可。设加的一行是第 0 行,怎么计算呢,发现与上面的类似(设 uu 为第 0 行的方案数,vv 为未被涂色的行数):

u2vu* 2^v

显然已经被涂色的行是没有两种方案的,而计算了被涂色的行对第 0 行的影响之后,未被涂色的行一定有两种方案
考虑某一行的涂色 a,ba, b(指颜色) 的对第 0 行的影响(限制)。

cdab\begin{matrix} \cdots & c & \cdots & d & \cdots\\ \vdots & \vdots & \vdots & \vdots & \vdots\\ \cdots & a & \cdots & b & \cdots \end{matrix}

, aa 在第 jj 行。
回想刚刚的两种方案,如果 a,ba, b 所在的列数同奇偶,那么 p=qp = q
证明:由于每一行与上一行的颜色中,要么同时改变偶数列,要么同时改变奇数列,所以 必然一起变化。
如果 a,ba, b 所在的列数不同奇偶,那么
证明:由于每一行与上一行的颜色中,要么偶数列,奇数列,必然有一个被改变,所以 每经过一行就要改变一次,一共经过了 jj 行。

这样的关系的前提是中间未被涂色的行有 2 种方案选择。也就是说,如果我们按照这样的方式限制第 0 行的两个元素,那么中间未被涂色的行一定有 2 种选择。
所以我们现在转而求在异或限制条件下,第 0 行的方案数。
如果有一个第 0 行限制 ,不妨设立并查集,将第 0 行的列 ii 拆为两个点 x2i,x2i+1x_{2i}, x_{2i + 1},表示 xx 列涂色 0 或 1。则我们合并 (2c,2d+p),(2c+1,2d+(1p))(2c, 2d + p), (2c + 1, 2d + (1 - p))(为了方便这里的 c 又变成颜色 c 所在的列号了),表示一旦确定了 c 涂什么颜色,d 就确定了,反之确定 d 也可以推出 c。
无解的判断是如果 (x2i,x2i+1)(x_{2i}, x_{2i + 1}) 在一个联通块,那么无解。
我们知道,如果有限制关系 ,那么确定了 cc 也就确定了 dd,所以我们对于限制关系再建立一个并查集(不拆点),合并 (c,d)(c, d)。最终会得到 cntcnt 个联通块,不难发现,联通块中任意一个确定,整个联通块的染色确定,所以一个联通块是有 2 种选择的。
若有 kk 行未被染色,则答案为:

2cnt+k12 ^ {cnt + k - 1}

代码

//  Created by Sengxian on 4/28/16.
//  Copyright (c) 2016年 Sengxian. All rights reserved.
//  BZOJ 2303 异或方程 + 并查集
#include <algorithm>
#include <iostream>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstring>
#include <cstdio>
#include <vector>
using namespace std;

inline int ReadInt() {
    static int n, ch;
    n = 0, ch = getchar();
    while (!isdigit(ch)) ch = getchar();
    while (isdigit(ch)) n = (n << 3) + (n << 1) + ch - '0', ch = getchar();
    return n;
}

const int maxn = 1000000 + 3;
struct unionset {
    int fa[maxn * 2];
    inline void init(int n) {
        for (int i = 0; i < n; ++i)
            fa[i] = i;
    }
    int getFa(int x) {
        return fa[x] == x ? x : fa[x] = getFa(fa[x]);
    }
    inline void unite(int x, int y) {
        x = getFa(x), y = getFa(y);
        fa[x] = y;
    } 
    inline bool same(int x, int y) {
        return getFa(x) == getFa(y);
    }
}u1, u2;

typedef pair<int, bool> pi;
vector<pi> G[maxn];
int n, m, k;

inline int mod_pow(int a, int b, int modu) {
    int res = 1;
    while (b) {
        if (b & 1) res = (long long)res * a % modu;
        a = (long long)a * a % modu;
        b >>= 1;
    }
    return res;
}

int main() {
    #ifndef ONLINE_JUDGE
        freopen("test.in", "r", stdin);
    #endif
    n = ReadInt(), m = ReadInt(), k = ReadInt();
    for (int i = 0, x, y; i < k; ++i) {
        x = ReadInt() - 1, y = ReadInt() - 1;
        G[x].push_back(pi(y, ReadInt()));
    }
    int cnt = 0;
    u1.init(m), u2.init(m * 2);
    for (int i = 0; i < n; ++i) {
        if (G[i].size() == 0) cnt++; //每一个未被的行有两种选择
        for (int j = 1; j < (int)G[i].size(); ++j) {
            int a = G[i][j].first, b = G[i][j - 1].first;
            bool p = G[i][j].second ^ G[i][j - 1].second;
            u1.unite(a, b);
            if ((a & 1) != (b & 1)) p ^= ((i + 1) & 1);
            u2.unite(a * 2, b * 2 + p), u2.unite(a * 2 + 1, b * 2 + !p);
        }
    }
    for (int i = 0; i < m; ++i)
        if (u2.same(i * 2, i * 2 + 1)) //统计矛盾
            return puts("0"), 0;
        else if (u1.fa[i] == i) cnt++; //统计联通块,每个联通块有两种选择
    printf("%d\n", mod_pow(2, cnt - 1, 1000000000));
    return 0;
}