Educational Codeforces Round 51 D Bicolorings
おもしろかった。情報オリンピックで出そう。
http://codeforces.com/contest/1051/problem/D
memo[i][j][k] : j 列目のタイルを形式iで塗ったときにコンポーネントがk個になる場合の数
ここで、形式iとは
形式0:1行目白, 2行目白
形式1:1行目白, 2行目黒
形式2:1行目黒, 2行目白
形式3:1行目黒, 2行目黒
これはビットをうまく使えば簡単に表現できるかも知れない
#include<cstdio> using namespace std; typedef long long int ll; static const int MAX_N = 1000; static const int MAX_K = 2 * MAX_N; static const ll MOD = 998244353; int n, k; ll memo[4][MAX_N][MAX_K + 1]; int main(){ scanf("%d %d", &n, &k); for(int i = 0; i < n; i++){ if(i == 0){ memo[0][i][1]++; memo[1][i][2]++; memo[2][i][2]++; memo[3][i][1]++; }else{ for(int j = 1; j <= k; j++){ if(j == 1){ memo[0][i][j] += memo[0][i - 1][j]; memo[3][i][j] += memo[3][i - 1][j]; }else{ memo[0][i][j] += memo[0][i - 1][j] + memo[1][i - 1][j] + memo[2][i - 1][j] + memo[3][i - 1][j - 1]; memo[1][i][j] += memo[0][i - 1][j - 1] + memo[1][i - 1][j] + memo[2][i - 1][j - 2] + memo[3][i - 1][j - 1]; memo[2][i][j] += memo[0][i - 1][j - 1] + memo[1][i - 1][j - 2] + memo[2][i - 1][j] + memo[3][i - 1][j - 1]; memo[3][i][j] += memo[0][i - 1][j - 1] + memo[1][i - 1][j] + memo[2][i - 1][j] + memo[3][i - 1][j]; } for(int l = 0; l < 4; l++) memo[l][i][j] %= MOD; } } } ll res = 0; for(int i = 0; i < 4; i++){ res += memo[i][n - 1][k]; res %= MOD; } printf("%lld\n", res); return 0; }