kojingharangの日記

Recruit Programming Contest 模擬練習会 B. ブロック並べ

22:36 |

• 赤ブロックR個、青ブロックB個を一列に並べる。連続する rn 個のうち赤が rk 個以上あるとだめ。連続する bn 個のうち青が bk 個以上あるとだめ。そんな並べ方は何通りあるか, mod 1,000,000,009で求めよ。
• 1≦R,B≦20
• 1≦rk≦rn≦9, 1≦bk≦bn≦9

• 最後に連続した赤/青の個数を持っておくのか？
• いや rn 個中何個だから置いていってずれたとき押し出されるのも状態に含めないとだめだ
• 直前の rn, bn 個をビットパターンで持っておけばよさげ
• 合わない
• ご飯
• 赤青を使った個数も持っておかないとだめだ

• 合わない
• 青置いた個数は計算できるから要らないか
• [置いた個数(%2)][赤を置いた個数][直前のrn個がそれぞれ赤かどうか][直前のbn個がそれぞれ青かどうか] = それが何通りあるか

• 合わない
• おわり

• 初期化してなかった。おうふ
• 初期化をしましょう

• accepted in practice

#define MOD 1000000009LL

int dp[2][21][512][512];

int main() {
	//ios::sync_with_stdio(false);
	int TESTS, R, B, rn, rk, bn, bk;
	cin>>TESTS;
	REP(test, TESTS) {
		CLEAR(dp, 0);
		int men=0;
		dp[men][0][0][0]=1;
		cin>>R>>B>>rn>>rk>>bn>>bk;
		REP(i, R+B) {
			CLEAR(dp[1-men], 0); // 初期化しましょう
			REP(cr, R+1) REP(ri, 1<<rn) REP(bi, 1<<bn) {
				int cb = i-cr;
				if(!(0<=cb && cb<=B)) continue;
				if(dp[men][cr][ri][bi]==0) continue;
				int nri = (ri<<1)&((1<<rn)-1);
				int nbi = (bi<<1)&((1<<bn)-1);
				if(POPCOUNT(nri)+1<rk && cr<R) dp[1-men][cr+1][nri|1][nbi] = (dp[1-men][cr+1][nri|1][nbi] + dp[men][cr][ri][bi]) % MOD;
				if(POPCOUNT(nbi)+1<bk && cb<B) dp[1-men][cr][nri][nbi|1] = (dp[1-men][cr][nri][nbi|1] + dp[men][cr][ri][bi]) % MOD;
			}
			men ^= 1;
		}
		ll ans = 0;
		REP(ri, 1<<rn) REP(bi, 1<<bn) ans = (ans + dp[men][R][ri][bi]) % MOD;
		
		cout<<ans<<endl;
	}
	
	return 0;
}

ツイートする