2303: [Apio2011]方格染色

Time Limit: 20 Sec Memory Limit: 256 MB
Submit: 561 Solved: 239
[Submit][Status]
Description

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

Input

输入的第一行包含三个整数n, m和k,分别代表表格的行数、列数和已被染
色的方格数目。
之后的k行描述已被染色的方格。其中第 i行包含三个整数xi, yi和ci,分别
代表第 i 个已被染色的方格的行编号、列编号和颜色。ci为 1 表示方格被染成红
色,ci为 0表示方格被染成蓝色。
Output

输出一个整数,表示可能的染色方案数目 W 模 10^9得到的值。(也就是说,如果 W大于等于10^9,则输出 W被10^9除所得的余数)。

对于所有的测试数据,2 ≤ n, m ≤ 106
,0 ≤ k ≤ 10^6
,1 ≤ xi ≤ n,1 ≤ yi ≤ m。

Sample Input

3 4 3

2 2 1

1 2 0

2 3 1

Sample Output

8
HINT

数据为国内数据+国际数据+修正版

鸣谢GYZ

Source


乍一看感觉是一道神题。。
首先判定是否有解就不知道怎么做了。。他还要求方案数。。
不过稍加分析就马上有想法了

我们先试着构造满足条件的矩阵,然后可以发现当第一行确定了之后,接下来每一行就只有两种方案了:分别是在每个奇数位异或1、每个偶数位异或1得到的序列(我不会告诉你就这个我想了好几个小时)。
这样貌似有些头绪了,至少可以判断是否有解了。

接下来是方案数。
按照上面的构造方法,我们只要求出第一行的方案数,然后乘上2^空行数就是ans了。
但是如何求第一行的方案数?是2^m吗?显然不是。。。我们发现有几列它们是互相关联的。
假设第二行第一列和第二列被涂上颜色,那么第一行如果确定了第一列,那么第二列也就跟着确定了。
于是乎,我们只要用个并查集,把每一行中的每一个有涂颜色的列都串在一起,最后求一下有几个连通块,然后第一行的方案数就是2^连通块数了。

回到第一个问题:如何判断是否有解?
(我不会告诉你我一开始想了半天写了个需要迭代来保证正确性的暴力,然后还以为不用迭代也是对的。。。就这个调了好久。。。)
首先一个很自然的想法就是暴力判矛盾,然后确定每一位。这个需要迭代若干次。。。看似不太科学,不过还是可以轻松水过的。。八中上面只要迭代15次就够了。。。
但是这并不是理想的算法。
怎么做呢?
看到那么多逻辑关系,应该马上就可以想到并查集或是2-SAT了(只要不像我那么逗)
并查集做法如下:
从第一行变换到每一行,所有的偶数位相对关系不会变,奇数位也是。
于是这是一个限制条件。
还有一个是奇数位和偶数位之间的关系。
这个要根据行号的奇偶来判断。
假设奇数位异或了p1次,偶数位异或了p2次。那么当前行号等于p1+p2+1。
根据行号的奇偶性可以得出p1+p2的奇偶性,然后就可以判断奇数位与偶数位之间的关系了。
然后就是代码了
PS 千万不要手贱,像我一样两个并查集都调乱了,调了一个小时T T。。一天就这么荒废过去了。。
总感觉apio要完挂了T T

巨丑无比的代码

#include <cstdio>
#include <cstring>
const int N = 1000000 + 9,MOD = 1000000000;
int f[N],son[N],lnk[N],nxt[N],v[N],fa[N],pre[N],n,wei[N],ec,m,k;
int tmp[100][100];
bool mark[N];
int getf(int x){return x == f[x] ? x : f[x] = getf(f[x]);}
inline void addedge(int x,int y,int z)
{
    nxt[++ec] = son[x];
    son[x] = ec;
    lnk[ec] = y;
    wei[ec] = z;
}
int getf1(int x)
{
    if (x == fa[x]) return x;
    int father = getf1(fa[x]);
    pre[x] ^= pre[fa[x]];
    return fa[x] = father;
}
bool add(int x,int y,int z)
{
    int fx = getf1(x),fy = getf1(y);
    if (fx != fy) {
        fa[fx] = fy;
        pre[fx] = pre[x] ^ pre[y] ^ z;
        return true;
    }else return !(pre[x] ^ pre[y] ^ z);
}
int calc()
{
    memset(v,-1,sizeof v);
    for (int i = 1; i <= m; ++i) fa[i] = i,pre[i] = 0;
    for (int i = son[1],p = -1,val; i; i = nxt[i]) {
        v[lnk[i]] = wei[i];
        if (p != -1 && !add(lnk[i],p,(val ^ wei[i])))
            return 0;
        p = lnk[i];
        val = wei[i];
    }
    for (int i = 1; i <= n; ++i) {
        int father = -1;
        for (int j = son[i]; j; j = nxt[j])
            if (father == -1) father = lnk[j];
            else {
                int fx = getf(father),fy = getf(lnk[j]);
                if (fx != fy) {
                    if (v[fx] != -1) f[fy] = fx;
                    else f[fx] = fy;
                }
            }
    }
    int ans = 1;
    for (int i = 1; i <= m; ++i) if (v[getf(i)] == -1) v[getf(i)] = 0,(ans *= 2) %= MOD;
    for (int i = 2; i <= n; ++i) {
        int p[2] = {-1,-1},val[2];
        for (int j = son[i]; j; j = nxt[j]) {
            if (p[lnk[j]&1] != -1)
                if (!add(p[lnk[j]&1],lnk[j],(val[lnk[j]&1] ^ wei[j])))
                    return 0;
            val[lnk[j]&1] = wei[j];
            p[lnk[j]&1] = lnk[j];
        }
        if (i == 2)
            i = 2;
        if (p[0] != -1 && p[1] != -1)
            if (!add(p[0],p[1],(((i - 1) & 1) ^ val[0] ^ val[1])))
                return 0;
    }
    for (int i = 1; i <= m; ++i)
        if (v[getf1(i)] == -1) v[getf1(i)] = 0;
    // for (int i = 1; i <= m; ++i) {
    //  getf1(i);
    //  printf("%d",pre[i]^v[getf1(i)]);
    // }puts("");
    for (int i = 2; i <= n; ++i)
        if (!son[i]) (ans *= 2) %= MOD;
    return ans;
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("2303.in","r",stdin);
    freopen("2303.out","w",stdout);
    #endif
    scanf("%d%d%d",&n,&m,&k);
    for (int i = 1; i <= m; ++i) f[i] = i;
    // for (int i = 1; i <= n; ++i)
    //  for (int j = 1; j <= m; ++j) tmp[i][j] = 2;
    for (int i = 1,x,y,z; i <= k; ++i) {
        scanf("%d%d%d",&x,&y,&z);
        //tmp[x][y] = z;
        addedge(x,y,z);
    }
    // for (int i = 1; i <= n; ++i) {
    //  for (int j = 1; j <= m; ++j)
    //      if (tmp[i][j] == 2) putchar('_');
    //      else printf("%d",tmp[i][j]);
    //  puts("");
    // }
    printf("%d\n",calc());
}

Comments

comments powered by Disqus
Copyright © 2013 lazycal of Shen Ben
Powered by Logdown and Greyshade
Favicon from The Noun Project