Coloring

好难的题目啊！

写个博客记录一下.

首先显然满足要求的一定是相邻行取反或者列取反的矩阵.画下图可推出来.

然后,分别考虑行列肯定是2^n,和2^m,可以看成确定一排后面的都确定了,也可以看成每一排都有两种选法.

然后考虑修改...和去重

重复即是两种情况都满足的,其实只有两种取法,即是黑白染色,确定一个点就可以确定是哪种选法.然后去判断修改是不是影响到我的去重了,假如影响到了我就不减.

然后就做完了...但是好绕啊)))网上的题解我也理解了很久,我自己的题解肯定自己理解的比较快叭~~~~~

好难喔~

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=1e6+5;
const int M=2;
const int mod=998244353;
const int iv2=(mod+1)/2;

struct date{
	ll ans;
	int cnt[N][M];//当前行/列投射到第1个列/行的值的次数.
	int f=0;//是不是已经产生了矛盾. 
	unordered_map<int,int>s[N];//记录下当前的值方便删除. 
	void del(int x,int y)
	{
		if(!s[x].count(y))	return;
		if(cnt[x][0]&&cnt[x][1])	f--;
		cnt[x][(y&1)^s[x][y]]--;
		s[x].erase(y);
		if(cnt[x][0]&&cnt[x][1])	f++;
		if(!cnt[x][0]&&!cnt[x][1])	
		ans=ans*2%mod;
	}
	void ins(int x,int y,int val)
	{
		if(!cnt[x][0]&&!cnt[x][1])		ans=ans*iv2%mod;
		if(cnt[x][0]&&cnt[x][1])		f--;
		s[x][y]=val;
		cnt[x][(y&1)^val]++;
		if(cnt[x][0]&&cnt[x][1])	f++;
	}
}r,c;

//用来去重. 
int cnt[2];
unordered_map<int,int>vis[N];
ll p[N<<2];
ll ans=0;
int main()
{
	int n,m,k;	
	scanf("%d%d%d",&n,&m,&k);
	p[0]=1;
	for(int i=1;i<=n+m;i++)	p[i]=p[i-1]*2%mod;
	r.ans=p[m];//行之间取反.
	c.ans=p[n];//列之间取反.
	for(int i=1;i<=k;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		r.del(y,x);
		c.del(x,y);
		if(vis[x].count(y))	cnt[vis[x][y]^(x&1)^(y&1)]--,vis[x].erase(y);
		if(z!=-1)
		{
			vis[x][y]=z;
			r.ins(y,x,z);c.ins(x,y,z);
			cnt[vis[x][y]^(x&1)^(y&1)]++;
		}
		ans=0;
		if(!r.f)	ans+=r.ans;
		if(!c.f)	ans+=c.ans;
		ans-=(!cnt[0]);
		ans-=(!cnt[1]);
		ans=(ans%mod+mod)%mod;
		printf("%lld\n",ans);
	}
	return 0;
}