---
tags: Programming Contest
---

# Codeforces #663 (Div. 2) 題解

[題目連結](https://codeforces.com/contest/1391)

## 心得

又繼續掉分了 (╯°□°)╯︵ ┻━┻

第二題卡牆，明明題目說只有 `R`, `D`，我思考時卻一直想成會有 `R`, `L`, `D`, `U`，然後我就去刻了個 BFS，卻發現會錯，還好最後有解出這題。第四題可惜，有想到 `N>=4 and M >= 4` 時無解，卻沒想出如何高速處理 `3xM` 或 `Nx3` 的情況，竟然得 dp…最後稱讚一下 editorial，比賽一結束就有了，而且有影片版本，雖然印度口音很重，但有字幕！

## A. Suborrays

看到官方題解嚇到了：Every permutation is good。比賽時我是將大的數字與小的數字交錯出現，沒仔細思考為什麼會對 XD，又是 bit 的，又是個數的，很難扯在一起啊。

## B. Fix You

因為只有 `R`, `D`，所以行李最後只有三種可能：

1. 到達右下角
2. 從矩陣右方離開
3. 從矩陣下方離開

所以答案就是將矩陣右方都改成向下、矩陣下方都改成向右。

## C. Cyclic Permutations

比賽時原本以為解不出來，後來竟然被我想出來了，值得慶祝，還好沒放棄 XD。
以下列出 **不是** cyclic permutation 的情況：

N = 3
[1 2 3] [3 2 1]
[1 3 2] [2 3 1]

N = 4
[1 2 3 4] [4 3 2 1]
[1 2 4 3] [3 4 2 1]
[1 3 4 2] [2 4 3 1]
[1 4 3 2] [2 3 4 1]

可以發現二點：

1. 左方的那些 permutations 與右方的那些 permutations 互為對稱。
2. 把 `N = 4` 的左方那些 permutations 的 1 拿掉，剩下數字減 1，會變成 `N = 3` 的所有 permutations。

可以推論 `N=k` 時 **不是** cyclic permutation 的數量是 `N = k - 1` 時的二倍。我們又知道 N = 3 時是 4，於是得到公式解 ：`N = k` 時，**不是** cyclic permutation 的數量為 $4 \cdot 2^{k-3} = 2^{k - 1}$。

題目所求就是 $N! - 2^{N - 1}$。

mod = 10**9 + 7
N = int(input())
fact = [1] * (N + 1)
for i in range(1, N + 1):
    fact[i] = fact[i - 1] * i % mod
ans = fact[N]
ans = ans - pow(2, N - 1, mod) + mod
ans = ans % mod
print(ans)

## D. 505

官方題解與影片都寫得不錯。

首先 `N >= 4 and M >= 4` 無解，因為他可以分成偶數個不重疊的 2x2 矩陣，偶數乘上奇數是偶數。另外，`N == 1 or M == 1`，直接輸出 0，給定的矩陣必為 good。剩下的情況得用 bitmask dp 來處理。

設 `dp[c][mask]` 為使前 `c` 個 cols 變成 good，且第 `c` 個 col 變成 `mask`，所需的最小操作數。mask 是 bitmask，例如 `mask = 0b110`，那代表我們要將該 col 變成 `[1, 1, 0]`。題目所求為 `min(dp[M - 1][mask] for mask in range(1 << N))`。

針對`dp[c][curr_mask]` 時，其轉移為枚舉 col `c - 1` 所有**可行** mask，取最小值，再加上將 col `c` 變成 `curr_mask` 的操作數：

dp[i][curr_mask] = min(
    [
        dp[i - 1][prev_mask]
        for prev_mask in range(1 << N)
        if is_valid(prev_mask, curr_mask, N)
    ]
) + make(state[i], curr_mask)

所謂 **可行** 是指 col `c` 的 `curr_mask` 與 col `c - 1` 的 `prev_mask` 不會構成總和為偶數的 2x2 子矩陣。實作上，可以透過一些位元操作在 O(1) 算出。將 col `c` 變成 `curr_mask` 的操作數也可以透過 `popcount` 與 `xor` 得到。

底下程式碼是 pypy。

def is_valid(prev_mask, curr_mask, N):
    bits = prev_mask ^ curr_mask
    if N == 2:
        return bits != 0b00 and bits != 0b11
    else:
        check1 = bits != 0b000 and bits != 0b001 and bits != 0b100
        check2 = bits != 0b111 and bits != 0b110 and bits != 0b011
        return check1 and check2


def solve():
    N, M = map(int, input().split())
    A = [list(map(int, input())) for _ in range(N)]

    if N >= 4 and M >= 4:
        return -1

    if N == 1 or M == 1:
        return 0

    state = [0] * M
    for c in range(M):
        for r in range(N):
            if A[r][c] == 1:
                state[c] |= 1 << (N - 1 - r)

    popcounts = [bin(x).count('1') for x in range(1 << N)]

    dp = [[N * M] * (1 << N) for _ in range(M)]

    for mask in range(1 << N):
        dp[0][mask] = popcounts[state[0] ^ mask]

    for i in range(1, M):
        for curr_mask in range(1 << N):
            dp[i][curr_mask] = min(
                [
                    dp[i - 1][prev_mask]
                    for prev_mask in range(1 << N)
                    if is_valid(prev_mask, curr_mask, N)
                ]
            ) + popcounts[state[i] ^ curr_mask]

    return min(dp[-1])


print(solve())

:::success
[< 回到所有題解](https://hackmd.io/@amoshyc/HkWWepaPv/)
:::