[APIO2011]方格染色

题解:

挺不错的一道题目

首先4个里面只有1个1或者3个1

那么有一个特性就是4个数xor为1

为什么要用xor呢?

在于xor能把相同的数消去

然后用一般的套路 看看确定哪些值能确定全部

yy一下就能发现第一行第一列能确定全部

然后接下来就简单了

随便推一下就能发现aij是由a11^a1i^aj1 (如何i,j都是偶数再^1)

然后这样我们枚举一下a11然后就能判断书a1i和aj1的关系

这个只要用带权并查集维护就行了

另外如果给出的固定的是a1i aj1的话 这个并查集的方案数就是1

然后就统计并查集数目就行了

原文地址:https://www.cnblogs.com/yinwuxiao/p/9020610.html