[bzoj2303][Apio2011]方格染色

技术[bzoj2303][Apio2011]方格染色 [bzoj2303][Apio2011]方格染色Sam和他的妹妹Sara有一个包含n×m个方格的表格。她们想要将其的每个方格都染成红色或蓝色。
出于

[bzoj2303][Apio2011]方形染色

萨姆和他的妹妹萨拉有一张nm个正方形的桌子。他们想把它的每个方块都染成红色或蓝色。

出于个人偏好,他们希望表格中每22的正方形区域包含奇数个(一个或三个)红色正方形。

但是昨晚,有人给桌子上的一些方块涂了颜色!萨姆和萨拉现在非常生气。然而,他们想知道是否有可能对剩余的方块进行着色,以便整个表单仍然能够满足他们的要求。如果可能,有多少染色方案可以满足他们的要求?

Description

萨姆和他的妹妹萨拉有一张nm个正方形的桌子。他们想把它的每个方块都染成红色或蓝色。

出于个人偏好,他们希望表格中每22的正方形区域包含奇数个(一个或三个)红色正方形。

但是昨晚,有人给桌子上的一些方块涂了颜色!萨姆和萨拉现在非常生气。然而,他们想知道是否有可能对剩余的方块进行着色,以便整个表单仍然能够满足他们的要求。如果可能,有多少染色方案可以满足他们的要求?

Input

输入的第一行包含三个整数n、m和K,表示表格的行数、列数和平方数。

后面的k线描述已经染色的方块。第I行包含三个整数\(x_i,y_i,c_i\),分别表示第I个染色方块的行号、列号和颜色。\(c_i\)为1表示方块被染成红色,而\(c_i\)为0表示方块被染成蓝色。

Output

输出一个整数,代表可能的染色方案数w模\ (10 9 \)。

Sample Input

3 4 3

2 2 1

1 2 0

2 3 1

Sample Output

HINT

\(2 \ leq n,m\leq10^6,0\leq k\leq10^6,1\leq x _ I \ leq n,1\leq y_i\leq m\)。

Solution

当红色为1,蓝色为0时,问题约束可以转化为要求每个22平方面积的异或和为1。

如果已经确定了第一行,那么每个后续行要么是前一行的奇数列xor 1,要么是前一行的偶数列xor 1。那么方案数是\(\(\large{2^{ 2 {空行数} \)。

现在需要确认是否有这样的合法第一行,即每两个方块之间的颜色XOR关系是否矛盾。

对于第I行中的每个染色点阵\(x,y\),如果它们的列数等于奇偶性,则它们在第一行中的关系为\(c _ x \;xor \;c _ y \);如果它们的列在奇偶性上不同,那么它已经对第一行进行了(i-1)转换,并且它们在第一行中的关系是\(c _ x \;xor \;c _ y \;xor \;(i-1)\)。

然后利用并集维护列数,合并对等体的染色格,记录它们与其父格的XOR关系(便于O(1)找出同一连通块的格之间的XOR关系,判断合法性)。第一行中的方案数量是\(\(\large{2^{ 2 {未染色的连接块的第一行的数量} \)。

#定义N 1000005

#定义M 100000000

typedef long long ll

结构网格{

int x,y,c;

bool friend运算符(网格a、网格b){ 0

if(a.x!=b.x)返回a . XB . x;

返回a . Yb . y;

}

} a[N];

国际c[n]/*col[1][i]^col[1][f[i]]*/,f[n],n,m,k,tot;

布尔b[N],v[N];

内联int gf(int k){ 0

if(f[k]==k)返回k;

int fa=gf(f[k]);

c[k]^=c[f[k]];

返回f[k]=fa;

}

内联bool chk(int x,int y,int t){ 0

int p=gf(x),q=gf(y);

if(p^q){

if(b[p]| | b[q])b[p]=b[q]=true;

f[p]=q;c[p]=c[x]^c[y]^t;

返回真;

}

否则返回(c[x]^c[y])==t;

}

内联int po(int x,int k){ 0

int ret=1;

while(k){ 0

如果(k1)ret=1ll * ret * x % M;

x=1ll * x * x % M;k=1;

}

返回ret

}

内嵌void Aireen(){ 0

n=read();m=read();k=read();

for(int I=1;I=k;I){ 0

a[i]=(网格){read(),read(),read()};

如果(a[i]。x==1) b[a[i]。y]=真;

v[a[i]。x]=真;

}

排序(一个1,一个1k);

for(int I=1;I=m;I)f[I]=I;

for(int i=2,x,y,t;I=k;I){ 0

一会儿。x==a[i-1]。x){ 0

x=a[i]。y;y=a[i-1]。y;

t=a[i]。c^a[i-1].c .

if((x1)^(y1)t^=((a[i].x-1)1);

if(!chk(x,y,t)){ 0

puts(' 0 ');返回;

}

我;

}

}

for(int I=1;I=m;(一)

if(gf(I)=I!b[I])tot;

for(int I=2;I=n;(一)

if(!v[I])tot;

printf('%d\n ',po(2,tot));

}

2017-05-03 17:56:48

内容来源网络,如有侵权,联系删除,本文地址:https://www.230890.com/zhan/116864.html

(0)

相关推荐

  • 互联网中元宇宙到底是什么东西

    技术互联网中元宇宙到底是什么东西这篇文章将为大家详细讲解有关互联网中元宇宙到底是什么东西,小编觉得挺实用的,因此分享给大家做个参考,希望大家阅读完这篇文章后可以有所收获。 元宇宙也称为形上宇宙

    攻略 2021年11月2日
  • 文明礼貌的内容,文明礼貌主要表现在哪些方面

    技术文明礼貌的内容,文明礼貌主要表现在哪些方面讲文明、有礼貌是有教养的直接表现文明礼貌的内容,也是做人最基本的要求。古语说:“诚于中而形于外。”文明礼貌是一个人美好心灵的自然流露,其实,做一个有教养的人更重要的是品德高尚

    生活 2021年10月19日
  • 怎么用Python在520俘获女神芳心

    技术怎么用Python在520俘获女神芳心这篇文章主要讲解了“怎么用Python在520俘获女神芳心”,文中的讲解内容简单清晰,易于学习与理解,下面请大家跟着小编的思路慢慢深入,一起来研究和学习“怎么用Python在52

    攻略 2021年11月2日
  • 香港服务器配置有哪些档次USA-IDC

    技术香港服务器配置有哪些档次USA-IDC香港服务器租用从配置标准来划分主要有以下几个类型标准配置的香港服务器一般标准配置香港服务器的构建和性能略好于廉价的香港VPS服务器。对于中小型企业、初创公司和组织最适合使用中等配

    礼包 2021年12月24日
  • JVM堆外内存泄漏故障排查的示例分析

    技术JVM堆外内存泄漏故障排查的示例分析本篇文章为大家展示了JVM堆外内存泄漏故障排查的示例分析,内容简明扼要并且容易理解,绝对能使你眼前一亮,通过这篇文章的详细介绍希望你能有所收获。 前言记录一次线上JVM堆外内存泄漏

    攻略 2021年10月23日
  • 动态神经网络综述阅读笔记

    技术动态神经网络综述阅读笔记 动态神经网络综述阅读笔记动态神经网络综述阅读笔记
    简单记录了一下,没有什么调理O.O
    Introduction
    神经网络结构设计发展:
    2012-2015:快速发展
    201

    礼包 2021年10月27日