#C241018B. 游客与染色
标签（Label）
- 并查集
- 观察+分析
网址（Website）
题解（Solution）
$\qquad$很重要的性质：知道第 $1$ 行和第 $1$ 列就能知道整个矩阵。
$\qquad$怎么想到的呢？从最开始开始推矩阵，就可以发现规律。
$\qquad$我这个傻货，直接去推矩阵的中间，然后没有发现这个性质。。。。。。
$\qquad$累积经验：做题之前，如果要求情况数，可以先枚举一种情况找规律——手跑一种推所有。
出题者题解
算法分析
算法 1
直接
$2^{nm}$ 次方枚举即可。期望得分 $10$。
算法 2
设 $a_{i,j}$ 为第 $i$ 行 $j$ 列的颜色，对于 $i,j>1$ 有 $a_{i,j} = a_{i-1,j} \oplus a_{i,j-1} \oplus a_{i-1,j-1}$。所以，当我们确定了第一行和第一列时整个矩阵可以被确定。对于空矩阵，任何填入第一行第一列的方式都是合法的，故答案为 $2^{n+m-1}$。 结合算法 1 期望得分 $30$。
算法 3
爆搜枚举第一行第一列的颜色即可。 结合算法 2 期望得分 $45$。
算法 4
观察发现一次涂色即为加入若干个“若 $x$ 行 $1$ 列为 $a$，则 $1$ 行 $y$ 列为 $b$ ”的限制。 把每行每列看作两个点 $u_0, u_1$，共 $2 \times (n+m)$ 个点，表示取值为 $0/1$。把限制看作加入边。则同一个连通块的点必须同时取。我们只需维护连通块个数即可。具体的，设两个点为 $u, v$，则我们连上 $u_0 - v_c, u_1 - v_{1-c}$。若此时存在点 $u$，使得 $u_0, u_1$ 在同一连通块中，则答案为 $0$。上述过程都可以用并查集维护。最后注意 $x=1$ 或 $y=1$ 的情况。时间复杂度 $O(n\alpha(n))$。期望得分 $100$。
代码（Code）
#include<bits/stdc++.h>
#include<vector>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define Rof(i,l,r) for(int i=l;i>=r;i--)
using namespace std;
#define P pair<int,int>
#define int long long
#define x first
#define y second
inline int rd(){
char c;bool f=false;while(!isdigit(c=getchar()))f=c=='-';int x=c^48;
while(isdigit(c=getchar())){x=(((x<<2)+x)<<1)+(c^48);}return f?-x:x;
}const int inf = 0x3f3f3f3f3f3f3f3f;
const int mod = 1e9+7;
const int N = 2012345;
bool ST;
int n,m,q,cnt;
int fa[N];
inline int find(int x){
if(fa[x]==x) return x;
return fa[x] = find(fa[x]);
}
void merge(int x,int y){
x = find(x), y = find(y);
if(x^y) fa[x] = y,cnt--;
}
bool flag = true;
int pw[N];
void Solve(){
n = rd(), m = rd(), q = rd(), cnt = 2*(n+m);
pw[0] = 1;For(i,1,n+m) pw[i] = pw[i-1]*2%mod;
iota(fa,fa+(n+m)*2+1,0);
printf("%lld\n",pw[cnt/2-1]);
while(q--){
int x = rd(), y = rd()+n, c = rd();
if(!flag){printf("0\n");continue;}
if(c) merge(x,y+n+m), merge(x+n+m,y);
else merge(x,y), merge(x+n+m,y+n+m);
if(find(x)==find(x+n+m)) flag=0,printf("0\n");
else printf("%lld\n", pw[cnt/2-1]);
}
}
bool ED;
signed main(){
ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
cerr<<abs(&ST-&ED)/1024./1024.<<"MB\n";
freopen("color.in","r",stdin);
freopen("color.out","w",stdout);
int T = 1, Tim = clock();
while(T--) Solve();
return cerr<<"TIME:"<<(clock()-Tim)/1000.,0;
}
