12063 Zeros and Ones

題目翻譯

給你兩個整數 n 和 k。

要你計算有多少個 n 位元的二進位正整數，滿足下面三個條件：

1. 0 和 1 的數量一樣多。
2. 這個數字可以被 k 整除。
3. 是 n 位元數，所以最高位必須是 1。

每筆測資輸出對應的方案數，格式為 Case x: ans。

輸入

第一行是測試案例數量。
接下來每行包含兩個整數 n $(2 \le n \le 64)$ 與 k $(k \gt 0)$。

輸出

對於每筆測資，輸出格式為 Case I: X，其中 I 是測資編號，X 是符合條件的數字個數。

解題思路

這題重點是位元 DP，直接枚舉所有長度 n 的二進位字串會太慢。

這份程式的狀態是 dp[p][cnt][rm]：

• p：還剩幾位要填
• cnt：目前放了幾個 1
• rm：目前前綴值對 k 的餘數

轉移只有兩種：

1. 這一位放 0，新餘數是 (rm * 2) % k
2. 這一位放 1，新餘數是 (rm * 2 + 1) % k

因為題目要求 n 位元正整數，最高位必須是 1，所以起點是 sol(n-1, 1, 1%k)（先固定最高位那個 1，剩下 n-1 位再遞迴）。

邊界與限制：

1. p == 0 時，如果 cnt == n/2 且 rm == 0 才算一組合法答案。
2. 計算目前已放的 0 數量 c0 = n - p - cnt。
3. 只有在 c0 < n/2 時才可以繼續放 0。
4. 只有在 cnt < n/2 時才可以繼續放 1。

另外 n 是奇數或 k == 0 時，答案直接是 0。

這樣可以把指數枚舉壓成可接受的 DP 複雜度。

程式碼

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define idonthavegirlfriend ios::sync_with_stdio(0), cin.tie(0);
#define pb push_back
#define yn(a) (a ? "Yes\n" : "No\n")
// #include <atcoder/fenwicktree>
// #include <atcoder/dsu>
// using namespace atcoder
// author Jackis666
int dp[65][65][105];  // 剩幾位,1's,rem
int n, k;
int sol(int p, int cnt, int rm) {
    if (p == 0) {
        return (cnt == n / 2 and rm == 0) ? 1 : 0;
    }
    int ans = 0;
    int c0 = n - p - cnt;
    if (dp[p][cnt][rm] >= 0) return dp[p][cnt][rm];
    if (c0 < n / 2) {
        ans += sol(p - 1, cnt, (rm * 2) % k);  // 填0
    }
    if (cnt < n / 2) {
        ans += sol(p - 1, cnt + 1, (rm * 2 + 1) % k);  // 填1
    }
    return dp[p][cnt][rm] = ans;
}
signed main() {
    idonthavegirlfriend
    int t;
    cin >> t;
    int idx = 0;
    while (t--) {
        cin >> n >> k;
        if (n % 2 != 0 or k == 0) {
            cout << "Case " << ++idx << ": " << 0 << "\n";
            continue;
        }
        memset(dp, -1, sizeof(dp));
        cout << "Case " << ++idx << ": " << sol(n - 1, 1, 1 % k)
             << "\n";  // 第一位一定1
    }
}