🔗 UVA-580 Critical Mass

tags: `數學(Math)`, `組合數學`, `動態規劃(DP)`

範例程式碼已於UVA、瘋狂程設(CPE)、ZeroJudge 上皆測試通過。

題意

給定一個長度為 $n$ 的字串，字串中只有 $L$ 和 $U$ 兩種字元，你的目的是使得字串中不能出現連續三個以上的 $L$ ，求有多少種排列方法。

約束條件

$n \leq 30$ 。

LuckyCat 的中文翻譯

思路：組合數學(排列組合) / 動態規劃(DP)

解法一：組合數學(排列組合)

只有 Python 能像範例這樣暴力預處理 $factorial$ ，其他語言可能會 overflow，例如 C++ 的 long long 也只能到 $20!$ 左右，因此需要用比較巧妙的方式計算 $comb$ ，可以參考範例的 C++ 寫法，或是將 $comb$ 寫成遞迴形式(Pascal’s triangle)。

由於出現連續三個以上 $U$ 的情況被視為不合法，因此可以反過來求合法的情況，再用總情況減去合法情況即可。

這裡的作法是枚舉單獨1個U 的數量 $u1$ 和連續2個U 的數量 $u2$ ，再使其不相鄰。為使這些組合皆不相鄰，可以用插空格的方法：假設有 $k$ 個 $L$ ，則有 $k+1$ 個空格可以插入，因此有 $C(k+1, u1+u2)$ 種插法。

而在這些空格中， $u1$ 和 $u2$ 又可以存在排列，因此又有 $\frac{(u1+u2)!}{u1! \cdot u2!}$ 種排列方式，即 $C(u1+u2, u1) = C(u1+u2, u2)$ 。

根據乘法原理，合法的情況數量為兩者相乘，即 $C(k+1, u1+u2) \times C(u1+u2, u1)$

複雜度分析

時間複雜度： $O(n^3)$ ，若預處理 $factorial$ 則為 $O(n^2)$ 。
空間複雜度： $O(1)$ ，若預處理 $factorial$ 則為 $O(n)$ 。

# from math import factorial as fact # built-in 的 fact 已經預先計算好部分數值了，速度較快
from functools import cache
@cache
def fact(n):
    return 1 if n <= 1 else n * fact(n-1)

while True:
    n = int(input())
    if n == 0:
        break
    legal = 0
    for u1 in range(n+1):
        for u2 in range(n//2+1):
            k = n - u1 - 2*u2 # 剩餘的L數量
            if k + 1 < u1 + u2: # 空格不夠
                break
            c1 = fact(k+1) // (fact(u1+u2) * fact(k+1-u1-u2)) # C(k+1, u1+u2) 插空格的方法
            c2 = fact(u1+u2) // (fact(u1) * fact(u2)) # (u1+u2)! / (u1! * u2!) 重複物排列
            legal += c1 * c2
    print(pow(2, n)- legal) # 總情況 - 合法情況

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 20;
#define endl '\n'

LL comb(int n, int k) {
    LL numerator = 1, denominator = 1;
    for (int i = 0; i < k; i++) {
        numerator *= n-i;
        if (numerator % (k-i) == 0) {
            numerator /= k-i;
        } else {
            denominator *= k-i;
        }
    }
    return numerator / denominator;
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n;
    while (cin >> n && n) {
        LL legal = 0;
        for (LL u1 = 0; u1 <= n; u1++) {
            for (LL u2 = 0; u2 <= n/2; u2++) {
                LL k = n - u1 - 2*u2;
                if (k + 1 < u1 + u2){
                    break;
                }
                LL c1 = comb(k+1, u1+u2);
                LL c2 = comb(u1+u2, u1);
                legal += c1 * c2; 
            }
        }
        LL ans = 1 << n;
        ans -= legal;
        cout << ans << endl;
    }
    return 0;
}

解法二：動態規劃(DP)

由於出現連續三個以上 $U$ 的情況被視為不合法，因此可以反過來求合法的情況，再用總情況減去合法情況即可。

令 $dp[i][j]$ 表示長度為 $i$ 的字串，後綴中有連續 $j$ 個 $U$ 的情況數，由於合法情況下最多只有 $2$ 個 $U$ ，因此 $j$ 只有 $0, 1, 2$ 三種情況。根據定義能寫出以下狀態轉移方程：

$dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2]$
$dp[i][1] = dp[i-1][0]$
$dp[i][2] = dp[i-1][1]$

答案即為 $2^n - \displaystyle\sum_{i=0}^{2} dp[n][i]$ 。

複雜度分析

時間複雜度： $O(n)$ 。
空間複雜度： $O(n)$ 。

from functools import cache

@cache
def f(i, j): # f(i, j) 表示長度為 i 的字串，後綴中有連續 j 個 U 的情況數
    if i == 0:
        return 1 if j == 0 else 0
    if j == 0:
        return f(i-1, 0) + f(i-1, 1) + f(i-1, 2)
    if j == 1:
        return f(i-1, 0)
    if j == 2:
        return f(i-1, 1)

while True:
    n = int(input())
    if n == 0:
        break
    print((1 << n) - sum(f(n, i) for i in range(3)))

#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int N = 35;
#define endl '\n'

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    int n;
    LL dp[N][3] = {0}; // dp[i][j] 表示長度為 i 的字串，後綴中有連續 j 個 U 的情況數
    dp[0][0] = 1;
    for (int i = 1; i < N; i++) {
        dp[i][0] = dp[i-1][0] + dp[i-1][1] + dp[i-1][2];
        dp[i][1] = dp[i-1][0];
        dp[i][2] = dp[i-1][1];
    }
    while (cin >> n && n) {
        cout << (1 << n) - dp[n][0] - dp[n][1] - dp[n][2] << endl;
    }
    return 0;
}