[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)

相关推荐

  • 基维百科,维基百科新规带来哪些改变

    技术基维百科,维基百科新规带来哪些改变为确保其平台的安全以及对抗各种骚扰行为,维基百科近日宣布正在实施新的行为准则基维百科。部分成员,尤其是女性和LGBTQ社区成员,抱怨平台上经常遭到会员编辑的“有毒行为”言语。该网站主

    生活 2021年10月31日
  • 考研复试什么时候,一般什么时候会公布考研复试线

    技术考研复试什么时候,一般什么时候会公布考研复试线2021年考研复试线的公布日期2021年研究生考试已经于2020年12月26~28日结束,目前全国各院校的初试成绩已经可以查询,成绩出来后可谓几家欢喜几家愁,各位考生对于

    生活 2021年10月24日
  • PostgreSQL中make_rel_from_joinlist函数分析

    技术PostgreSQL中make_rel_from_joinlist函数分析这篇文章主要介绍“PostgreSQL中make_rel_from_joinlist函数分析”,在日常操作中,相信很多人在PostgreSQL

    攻略 2021年11月10日
  • htmltextarea宽度如何设置(htmltextarea怎么设置高度)

    技术html textarea如何设置大小本篇内容介绍了“html textarea如何设置大小”的有关知识,在实际案例的操作过程中,不少人都会遇到这样的困境,接下来就让小编带领大家学习一下如何处理这些情况吧!希望大家仔

    攻略 2021年12月13日
  • ps怎么做倒影,倒影后期ps是怎么做出来的

    技术ps怎么做倒影,倒影后期ps是怎么做出来的手机一键制作“倒影”特效ps怎么做倒影:想给照片后期制作成“倒影”画面,小月分享一个方便快捷的方法,基本一键制作。比如:下图的冰雪城堡倒影特效原图就是一张城堡雪景图如果想更逼

    生活 2021年11月1日
  • html5是什么缩写(html5缩写成h5)

    技术html5是什么的缩写这篇文章给大家分享的是有关html5是什么的缩写的内容。小编觉得挺实用的,因此分享给大家做个参考,一起跟随小编过来看看吧。 html5是HyperText Marku

    攻略 2021年12月13日