Codeforces ECR #114 : E. Coloring

こちらはなんとか本番通してるな。
https://codeforces.com/contest/1574/problem/E

問題

N*Mのグリッドの各セルに0か1の値を入れることを考える。
値の埋め方が美しいとは、どの2*2領域も0と1が2個ずつ入る場合を意味する。

クエリを順次満たすような値の埋め方は何通りあるか、適宜答えよ。

• 指定されたマスの値が0/1で指定される
• 指定されたマスの値の指定が解除される。

解法

値の埋め方は以下の2通りである。

• 列方向に010101…と01が交互に並ぶ。行ごとに0スタートと1スタートが入れ替わっても良い。
• 行方向に010101…と01が交互に並ぶ。列ごとに0スタートと1スタートが入れ替わっても良い。
• 01が完全に市松模様を成す場合、上記両方を満たす点に注意。

値の指定がされるごとに、上記パターンをそれぞれ取りうるかどうかを判定しよう。
例えば1つ目の条件は、列方向にみて01が交互に並ばない列が登場した場合、取れない。
もし1つ目の条件を満たす場合、値が未指定の行がn個あれば、01どちらスタートかで2^n通りの組み合わせが取れる。

int W,H,K;
const ll mo=998244353;

unordered_map<int,int> M[1303030];
int P[2];
int Rpat[3];
int Cpat[3];
int NR[1303030],NC[1303030];
int NRpat[1303030][2],NCpat[1303030][2];
ll p2[1303030];


void clear(int x,int y) {
	if(M[x].count(y)==0) return;
	int c=M[x][y];
	M[x].erase(y);
	
	P[(x^y^c)&1]--;
	
	Cpat[NC[x]]--;
	NCpat[x][(y^c)&1]--;
	NC[x]=2-(NCpat[x][0]>0)-(NCpat[x][1]>0);
	Cpat[NC[x]]++;

	Rpat[NR[y]]--;
	NRpat[y][(x^c)&1]--;
	NR[y]=2-(NRpat[y][0]>0)-(NRpat[y][1]>0);
	Rpat[NR[y]]++;
	
	
}

void add(int x,int y,int c) {
	M[x][y]=c;
	P[(x^y^c)&1]++;
	
	Cpat[NC[x]]--;
	NCpat[x][(y^c)&1]++;
	NC[x]=2-(NCpat[x][0]>0)-(NCpat[x][1]>0);
	Cpat[NC[x]]++;

	Rpat[NR[y]]--;
	NRpat[y][(x^c)&1]++;
	NR[y]=2-(NRpat[y][0]>0)-(NRpat[y][1]>0);
	Rpat[NR[y]]++;
	
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d%d",&W,&H,&K);
	FOR(i,W) NC[i]=2, Cpat[2]++;
	FOR(i,H) NR[i]=2, Rpat[2]++;
	p2[0]=1;
	FOR(i,1302020) p2[i+1]=p2[i]*2%mo;
	
	while(K--) {
		scanf("%d%d%d",&x,&y,&k);
		x--,y--;
		clear(x,y);
		if(k>=0) add(x,y,k);
		
		ll ret=0;
		/*
		cout<<Cpat[0]<<Cpat[1]<<Cpat[2]<<endl;
		cout<<Rpat[0]<<Rpat[1]<<Rpat[2]<<endl;
		cout<<P[0]<<P[1]<<endl;
		*/
		if(Cpat[0]==0) ret+=p2[Cpat[2]];
		if(Rpat[0]==0) ret+=p2[Rpat[2]];
		if(P[0]==0) ret--;
		if(P[1]==0) ret--;
		cout<<(ret+mo)%mo<<endl;
		
	}
	
	
}

まとめ

この01の埋め方のパターンは過去何度か見たしね。