kmjp's blog

競技プログラミング参加記です

CADDi 2018 : F - Square

手間取ったけど最終的にはすんなり。
https://atcoder.jp/contests/caddi2018/tasks/caddi2018_d

問題

N*Nの行列Aを考える。
各要素は0/1の2値のいずれかを取る。
うち、一部の要素は値が指定されている。

この行列において、1≦i<j≦Nであるi,jに対し、(i,i)-(j,j)の矩形領域中の1の数が偶数であるようなものは何通りか。

解法

A(i,j)は、|i-j|>2の場合A(i,j)=A(j,i)である。
(i,i)-(j-1,j-1)、(i+1,i+1)-(j,j)、(i,i)-(j,j)がいずれも1が偶数回出るという条件より、A(i,j)+A(j,i)は偶数でなければならないためである。

よって、|i-j|>2におけるA(i,j)の組み合わせは容易に求めることができる。
あとは|i-j|≦2の場合を考える。これは端からDPしていけばよい。
まず(1,1)-(2,2)の4マスの値を総当たりすることを考える。
(i-1,i-1)-(i,i)の4値がわかっているとき、(i-1,i-1)-(i+1,i+1)の組み合わせをbitdpの要領で総当たりしていく、という形で(i,i)-(i+1,i+1)の4値として取れる値が確定するので、順次DPして組み合わせを求めることができる。

int N,M;
int A[101010],B[101010],C[101010];
ll mo=998244353;

ll modpow(ll a, ll n = mo-2) {
	ll r=1;a%=mo;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

map<pair<int,int>,int> mp;

ll dp[101010][1<<4];

int out(int x,int y,int val) {
	if(mp.count({x,y})==0) return 0;
	if(mp[{x,y}]==(val&1)) return 0;
	return 1;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>M;
	FOR(i,M) {
		cin>>A[i]>>B[i]>>C[i];
		A[i]--,B[i]--;
		mp[{A[i],B[i]}]=C[i];
		if(abs(A[i]-B[i])>2) {
			if(mp.count({B[i],A[i]}) && mp[{B[i],A[i]}]!=C[i]) return _P("0\n");
			mp[{B[i],A[i]}]=C[i];
		}
	}
	
	ll fr=0;
	FOR(i,N) fr+=N-(min(N-1,i+2)-max(i-2,0)+1);
	FORR(m,mp) if(abs(m.first.first-m.first.second)>2) fr--;
	fr/=2;
	ll pat=modpow(2,fr);
	
	int mask;
	FOR(mask,1<<4) if(__builtin_popcount(mask)%2==0) {
		int ng=0;
		FOR(y,2) FOR(x,2) ng|=out(x,y,(mask>>(y*2+x))%2);
		if(ng==0) dp[1][mask]++;
	}
	
	for(i=2;i<N;i++) {
		FOR(mask,1<<5) if(__builtin_popcount(mask)%2==0) {
			if(out(i,i,mask>>4)) continue;
			if(out(i-1,i,mask>>3)) continue;
			if(out(i-2,i,mask>>2)) continue;
			if(out(i,i-1,mask>>1)) continue;
			if(out(i,i-2,mask>>0)) continue;
			int mask2;
			FOR(mask2,1<<4) if(__builtin_popcount(mask2)%2==0) {
				int nmask=(mask2>>3)&1;
				nmask |= ((mask>>1)&1)<<1;
				nmask |= ((mask>>3)&1)<<2;
				nmask |= ((mask>>4)&1)<<3;
				if(__builtin_popcount(nmask)%2==0) (dp[i][nmask]+=dp[i-1][mask2])%=mo;
			}
		}
	}
	
	ll ret=0;
	FOR(i,1<<4) ret+=dp[N-1][i];
	cout<<ret%mo*pat%mo<<endl;
	
	
}

まとめ

だいぶ手間取ってしまった。