Educational Codeforces Round 51

ABCD解いて443位でした。可もなく不可もなくといった感じ。Fの解法がめっちゃ気になっているので別記事にします。

C - Vasya and Multisets

1回だけ現れる要素が偶数種類だったら同じ種類ずつ振り分けて、複数回現れる要素を片方にまとめる。

1回だけ現れる要素の種類が奇数だったら3回以上の現れるものから1個だけもらってきて、残りは↑と同様に振り分ける。

D - Bicolorings

列まで見て、個のcomponentがあって右端がBB/BW/WB/WW

int main() {
    i64 n, K;
    cin >> n >> K;
    
    if (n == 1) {
        cout << 2 << endl;
        return 0;
    }
    
    vvvi dp(n + 1, vvi(2 * n + 1, vi(4)));
    dp[1][1][0] = 1;
    dp[1][1][3] = 1;
    dp[1][2][1] = 1;
    dp[1][2][2] = 1;
    
    for (int i = 1; i < n; i++) {
        for (int k = 1; k <= 2 * n; k++) {
            dp[i + 1][k][0] = dp[i][k][0] + dp[i][k][1] + dp[i][k][2] + dp[i][k - 1][3];
            dp[i + 1][k][0] %= MOD;
            dp[i + 1][k][3] = dp[i][k - 1][0] + dp[i][k][1] + dp[i][k][2] + dp[i][k][3];
            dp[i + 1][k][3] %= MOD;
            if (k >= 2) {
                dp[i + 1][k][1] = dp[i][k - 1][0] + dp[i][k][1] + dp[i][k - 2][2] + dp[i][k - 1][3];
                dp[i + 1][k][1] %= MOD;
                dp[i + 1][k][2] = dp[i][k - 1][0] + dp[i][k - 2][1] + dp[i][k][2] + dp[i][k - 1][3];
                dp[i + 1][k][2] %= MOD;
            }
        }
    }
    
    i64 ans = (dp[n][K][0] + dp[n][K][1] + dp[n][K][2] + dp[n][K][3]) % MOD;
    cout << ans << endl;
}