[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