传送门
思路
很不错的一道题，用到的东西不深，但是要想到确实需要一定思维。
一开始我想的是动态规划，发现如果要设状态需要知道一个格子左边，上边和左上边三个格子的状态。然后发现转移时还要枚举右上角是什么，有点麻烦，但是应该可做。
思考题目时，如果题目不是一眼题，即使没有部分分，也应该从两个方面去想：
1. 数据规模较小的情况（如果题目的正解是多项式算法，那么最好往多项式算法去想，这时就不要纠结于指数级算法了）
2. 特殊情况，比如较少限制条件的情况
但是我忘记了考虑特殊情况，于是就凉了。
考虑一下，如果没有人来涂色，答案将会是多少。考虑逐层构造，发现，当构造完第一行时（第一行本身没有限制），第二行只需要知道第一个列是什么，就能唯一确定第二行。推广一下，便能发现：只要确定了第一行和第一列，那么就能得到唯一的构造方法。这跟普及组的熄灯问题是类似的。
现在我们把涂了的颜色加进来，看看会有哪些影响。影响无非就是原来的某个方案不符合已经涂色的内容。如果我们能够通过已经涂色的倒推出还没有涂色的，那么问题也差不多解决了。
下面就需要一些思维高度了。我们将题意转换一下，将颜色抽象为
0
0
和 1，则一个
2×2
2
×
2
的方阵里要么出现了
3
3
个 0，要么出现了
3
3
个 1。这等价于是说这个
2×2
2
×
2
的方阵异或和为
1
1
。
对于 (x,y)(x,y>1)，我们将左上角为
(1,1)∼(x−1,y−1)
(
1
,
1
)
∼
(
x
−
1
,
y
−
1
)
的所有
2×2
2
×
2
的方阵中的四个元素都选择一遍（要重复选择，因为异或的性质，选偶数次等价于没有选），那么这些元素的异或和显然与
(x−1)×(y−1)
(
x
−
1
)
×
(
y
−
1
)
有关（因为每个方阵的四个数的异或和为
1
1
，共有 (x−1)×(y−1) 个方阵）。若上式为奇数，则异或和为
1
1
，否则为 0。又因为异或的性质，可以发现，这么选等价于只选择了
(1,1),(x,1),(1,y),(x,y)
(
1
,
1
)
,
(
x
,
1
)
,
(
1
,
y
)
,
(
x
,
y
)
这四个方格。换句话说，我们知道了这四个数的异或和！
我们枚举
(1,1)
(
1
,
1
)
是
0
0
还是 1，就能得到两个数的异或和，这可以用带关系的并查集或者带反集合的并查集解决。如果出现了非法的情况，说明无解。最终的答案取决于两种颜色都能选的集合的个数。细节留给你们，我将会在参考代码后给出。
参考代码
丑
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <cassert>
#include <cctype>
#include <climits>
#include <ctime>
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <queue>
#include <deque>
#include <map>
#include <set>
#include <bitset>
#include <list>
#include <functional>
typedef long long LL;
typedef unsigned long long ULL;
using std::cin;
using std::cout;
using std::endl;
typedef int INT_PUT;
INT_PUT readIn()
{
INT_PUT a = 0; bool positive = true;
char ch = getchar();
while (!(ch == '-' || std::isdigit(ch))) ch = getchar();
if (ch == '-') { positive = false; ch = getchar(); }
while (std::isdigit(ch)) { a = a * 10 - (ch - '0'); ch = getchar(); }
return positive ? -a : a;
}
void printOut(INT_PUT x)
{
char buffer[20]; int length = 0;
if (x < 0) putchar('-'); else x = -x;
do buffer[length++] = -(x % 10) + '0'; while (x /= 10);
do putchar(buffer[--length]); while (length);
}
const int mod = int(1e9);
const int maxn = int(1e6) + 5;
int n, m, k;
int x[maxn];
int y[maxn];
int c[maxn];
struct DS
{
int parent[maxn * 4];
int color[maxn * 4];
void clear(int size)
{
for (int i = 1; i <= size; i++)
parent[i] = i;
for (int i = 1; i <= size; i++)
color[i] = -1;
}
int find(int x)
{
return x == parent[x] ? x : (x = find(parent[x]));
}
bool unite(int x, int y)
{
if (~color[find(x)] && ~color[find(y)] && color[find(x)] != color[find(y)])
return false;
color[find(x)] = std::max(color[find(x)], color[find(y)]);
parent[find(y)] = find(x);
return true;
}
bool judge(int x, int y)
{
return find(x) == find(y);
}
} ds;
LL power(LL x, int y)
{
LL ret = 1;
while (y)
{
if (y & 1) ret = ret * x % mod;
x = x * x % mod;
y >>= 1;
}
return ret;
}
void run()
{
n = readIn();
m = readIn();
k = readIn();
bool bset[2] = {};
for (int i = 1; i <= k; i++)
{
x[i] = readIn();
y[i] = readIn();
c[i] = readIn();
if (x[i] == 1 && y[i] == 1)
bset[c[i]] = true;
}
for (int i = 1; i <= k; i++)
{
x[i]--;
y[i]--;
}
int ans = 0;
int delta = n + m - 2;
#define THIS(x) (x)
#define ANTI(x) ((x) + delta)
if (!bset[0])
{
bool bOk = true;
ds.clear(delta << 1);
for (int i = 1; i <= k; i++)
{
if (!x[i] && !y[i])
continue;
else if (!x[i])
{
if (~ds.color[ds.find(THIS(y[i]))] &&
ds.find(THIS(y[i])) != c[i])
{
bOk = false;
break;
}
ds.color[ds.find(THIS(y[i]))] = c[i];
ds.color[ds.find(ANTI(y[i]))] = !c[i];
}
else if (!y[i])
{
if (~ds.color[ds.find(THIS(m - 1 + x[i]))] &&
ds.find(THIS(m - 1 + x[i])) != c[i])
{
bOk = false;
break;
}
ds.color[ds.find(THIS(m - 1 + x[i]))] = c[i];
ds.color[ds.find(ANTI(m - 1 + x[i]))] = !c[i];
}
else
{
if ((x[i] & 1) && (y[i] & 1))
{
if (!ds.unite(THIS(m - 1 + x[i]), ANTI(y[i])) ||
!ds.unite(ANTI(m - 1 + x[i]), THIS(y[i])) ||
ds.judge(THIS(m - 1 + x[i]), ANTI(m - 1 + x[i])) ||
ds.judge(THIS(y[i]), ANTI(y[i])))
{
bOk = false;
break;
}
}
else
{
if (!ds.unite(THIS(m - 1 + x[i]), THIS(y[i])) ||
!ds.unite(ANTI(m - 1 + x[i]), ANTI(y[i])) ||
ds.judge(THIS(m - 1 + x[i]), ANTI(m - 1 + x[i])) ||
ds.judge(THIS(y[i]), ANTI(y[i])))
{
bOk = false;
break;
}
}
}
}
if (bOk)
{
int ex = 0;
for (int i = 1; i <= (delta << 1); i++)
{
if (ds.parent[i] != i) continue;
if (!~ds.color[i])
ex++;
}
ex >>= 1;
ans = (ans + power(2, ex)) % mod;
}
}
if (!bset[1])
{
bool bOk = true;
ds.clear(delta << 1);
for (int i = 1; i <= k; i++)
{
if (!x[i] && !y[i])
continue;
else if (!x[i])
{
if (~ds.color[ds.find(THIS(y[i]))] &&
ds.find(THIS(y[i])) != c[i])
{
bOk = false;
break;
}
ds.color[ds.find(THIS(y[i]))] = c[i];
ds.color[ds.find(ANTI(y[i]))] = !c[i];
}
else if (!y[i])
{
if (~ds.color[ds.find(THIS(m - 1 + x[i]))] &&
ds.find(THIS(m - 1 + x[i])) != c[i])
{
bOk = false;
break;
}
ds.color[ds.find(THIS(m - 1 + x[i]))] = c[i];
ds.color[ds.find(ANTI(m - 1 + x[i]))] = !c[i];
}
else
{
if (!((x[i] & 1) && (y[i] & 1)))
{
if (!ds.unite(THIS(m - 1 + x[i]), ANTI(y[i])) ||
!ds.unite(ANTI(m - 1 + x[i]), THIS(y[i])) ||
ds.judge(THIS(m - 1 + x[i]), ANTI(m - 1 + x[i])) ||
ds.judge(THIS(y[i]), ANTI(y[i])))
{
bOk = false;
break;
}
}
else
{
if (!ds.unite(THIS(m - 1 + x[i]), THIS(y[i])) ||
!ds.unite(ANTI(m - 1 + x[i]), ANTI(y[i])) ||
ds.judge(THIS(m - 1 + x[i]), ANTI(m - 1 + x[i])) ||
ds.judge(THIS(y[i]), ANTI(y[i])))
{
bOk = false;
break;
}
}
}
}
if (bOk)
{
int ex = 0;
for (int i = 1; i <= (delta << 1); i++)
{
if (ds.parent[i] != i) continue;
if (!~ds.color[i])
ex++;
}
ex >>= 1;
ans = (ans + power(2, ex)) % mod;
}
}
printOut(ans);
}
int main()
{
run();
return 0;
}
细节
（这取决于具体实现）首先看有没有对
(1,1)
(
1
,
1
)
染色，如果有，则只有一种情况，否则
(1,1)
(
1
,
1
)
的颜色有两种情况。
对于所有对第一行或者对第一列（除了
(1,1)
(
1
,
1
)
）的染色，我们将所在被染位置所在集合进行标记，标记为染成了什么颜色，相应的它的反集合也要进行标记。如果它已经被标记了并且颜色不同，说明方案不合法。
进行并查集的合并操作时，我们同样先检查这两个集合是否已经被染色。若已经被染色了，且染的颜色不同，说明不合法，否则将新的集合也染上相应颜色。
最后，我们看并查集中有多少个集合没有被打上染色标记。设该值为
x
x
，显然，由于反集合与原集合有对称性，忽视反集合后应该有 x2 个集合没有被打上染色标记。那么在这种情况下的答案为
2x
2
x
。最终答案为（至多）两种情况的答案之和。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
