BZOJ 2303 - [Apio2011]方格染色

#思维 #并查集

Published on 2016-04-29

描述

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

分析

我希望描述的尽量清晰，不跳跃。
设行数为 $n$ ，列数为 $m$ 如果没有限制，那么合法的方案数为：

2^m * 2^{n - 1}

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

上一行奇数列不变，偶数列取反。
上一行偶数列不变，奇数列取反。

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

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

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

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

u* 2^v

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

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

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

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

2 ^ {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;
}

BZOJ 4069 - [Apio2015]巴厘岛的雕塑 BZOJ 4521 - [Cqoi2016]手机号码

Sengxian's Blog

BZOJ 2303 - [Apio2011]方格染色

描述

分析

代码