AtCoder ARC #036 : C - 偶然ジェネレータ

ちょっと苦戦。
http://arc036.contest.atcoder.jp/tasks/arc036_c

問題

0,1,?で構成されるN文字の文字列Sがある。
?は0か1に置き換えることができる。

Sの任意の連続部分文字列において、0と1の数の差がK以下となるような?の置き換え方が何通りあるか答えよ。

解法

P(位置,(0の数)-(1の数)の最小値,(0の数)-(1の数)の最大値,(0の数)-(1の数))をある位置までの条件を満たす組み合わせとする。
あとはこのPについて、((0の数)-(1の数)の最小値)-((0の数)-(1の数)の最大値)がK以下である範囲で順次DPで値を更新していけば良いのだが、このままではO(N*K^3)かかりTLEする。

実は、Pの後ろの３つの引数、(0の数)-(1の数)の最小値,(0の数)-(1の数)の最大値,(0の数)-(1の数)はすべて持つ必要はない。

例えばP(10,-2,2,1)とP(10,-1,3,2)は後ろ3つの引数は1ずつずれている。
しかし後ろの引数(-2,2,1)と(-1,3,2)は、全体を平行移動しただけで、どちらもこの後の0,1の出方によって0と1の差がK以下かそうでないかの判定は完全に一致する。
そのため、(-2,2,1)と(-1,3,2)もどちらもどれか１か所の値をそろえるように平行移動し、(0,4,3)と同じとみなすことができる。
こうすると引数のうち１つ、(0の数)-(1の数)の最小値を削除することができ、O(N*K^2)で解ける。

int N,K;
string S;
ll mo=1000000007;
ll M[2][302][302];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	
	cin>>N>>K>>S;
	M[0][0][0]=1;
	FOR(i,N) {
		int cur=i&1,tar=cur^1;
		ZERO(M[tar]);
		
		FOR(x,K+1) FOR(y,K+1) if(M[cur][x][y]) {
			ll& c=M[cur][x][y];
			if(S[i]=='0' || S[i]=='?') {
				if(y>0) (M[tar][x][y-1] += c)%=mo;
				if(y==0 && x<K) (M[tar][x+1][0] += c)%=mo;
			}
			if(S[i]=='1' || S[i]=='?') {
				if(y<x) (M[tar][x][y+1] += c)%=mo;
				if(y==x && y<K) (M[tar][x+1][x+1] += c)%=mo;
			}
		}
	}
	
	ll ret=0;
	FOR(x,K+1) FOR(y,K+1) ret += M[N%2][x][y];
	cout<<ret%mo<<endl;
}

まとめ

この状態数を１個減らすテク、SRMで過去に出た気がするけどいつの回か思い出せない…。