【Educational Codeforces】D - Bicolorings【Round 51】
問題概要
2列n行のマス目を白黒に塗り分ける。塗り分けた後、区画がk個できるような塗り分け方の数を求めよ。結果はかなり大きい数になるため、998244353で割ったあまりを出力せよ。
制約
- 1 <= n <= 1000
- 1 <= k <= 2n
考察
ぱっと見DPっぽいのでDPをする。
(黒,黒),(黒,白),(白,黒),(白,白)の4通りを毎行考えて、区画が増える場合とそうでない場合に分けてそれぞれ漸化式を考える。
dp[何行目まで見た][そこまでの区画数][左の塗り分け][右の塗り分け]とすると、求めるのはのはず。
ACコード(C++🔆)
/* (0,1,2,3) = ((黒,黒),(黒,白),(白,黒),(白,白)) */ const int MOD = 998244353; #define ADD(a,b) a=(a+ll(b))%MOD ll dp[1010][2020][4][4]; signed main() { SS(int,N,K); // 初期値 dp[0][1][0][0] = 1; dp[0][2][0][1] = 1; dp[0][2][0][2] = 1; dp[0][1][0][3] = 1; REP(i,N-1) REP(j,1,2*N+1) REP(a,4) REP(b,4) REP(c,4) { if (b==0 or b==3) { if(b==c) ADD(dp[i+1][j][b][c],dp[i][j][a][b]); else ADD(dp[i+1][j+1][b][c],dp[i][j][a][b]); } else { // (b,c) = (1,2), (2,1) if (b*c==2) ADD(dp[i+1][j+2][b][c],dp[i][j][a][b]); else ADD(dp[i+1][j][b][c],dp[i][j][a][b]); } } ll res = 0; REP(a,4) REP(b,4) ADD(res,dp[N-1][K][a][b]); P(res); }
