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;
}