Codeforces #594 Div1 A. Ivan the Fool and the Probability Theory

Bで躓いていまいちだった回。
https://codeforces.com/contest/1239/problem/A

問題

H*Wのグリッドを白黒に塗り分ける。
その際、各セルの、隣接セルに、同色のセルが最大1個となるケースは何通りか。

解法

一番上の行を左から埋めることを考える。
同じ色は3つ連続できないため、直前2個のセルの色を持ってDPしていけばよい。
もし同じ色の2つ連続が1か所でもある場合、以降の行は上の行と同じでなければならないので、各行の色は確定する。

行と列を入れ替えても同様。
ただし、完全に市松模様のケースは両方で二重カウントしてしまうので、そこだけ引いておこう。

int H,W;
const ll mo=1000000007;

ll dp[101010][2][2];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>H>>W;
	
	ll ret=0;
	FOR(i,2) {
		ZERO(dp);
		
		if(W==1) {
			ret+=2;
		}
		else {
			dp[2][0][1]=1;
			dp[2][1][0]=1;
			dp[2][0][0]=1;
			dp[2][1][1]=1;
			for(j=3;j<=W;j++) {
				dp[j][0][0]=dp[j-1][1][0];
				dp[j][1][1]=dp[j-1][0][1];
				dp[j][0][1]=(dp[j-1][1][0]+dp[j-1][0][0])%mo;
				dp[j][1][0]=(dp[j-1][0][1]+dp[j-1][1][1])%mo;
			}
			
			ret+=dp[W][0][0]+dp[W][0][1]+dp[W][1][0]+dp[W][1][1];
		}
		swap(W,H);
	}
	ret+=mo-2;
	cout<<ret%mo<<endl;
	
	
}

まとめ

ここまではよかったんだけどね。