BZOJ 1072 [SCOI2007] 排列 perm —— 狀壓 DP 計數可被 d 整除的排列數

BZOJ 1072：給定數字串 s（長度 ≤ 10）與正整數 d ≤ 1000，求 s 的全排列中能被 d 整除的個數（允許前導 0）。T ≤ 15 組測試。經典狀壓 DP模板題。

一、狀態定義

f[mask][rem]：已選數字集合為 mask，當前排列對 d 取模餘數為 rem 的方案數。
mask 共 2^n 狀態，rem 共 d 狀態。

二、轉移方程

從 mask 嘗試添加一個未選位置 i：

int newMask = mask | (1<

三、去重處理（相同數字視為不可區分）
若 s 含重複數字，直接 DP 會過度計數。標準技巧：按位置順序強制首次選取。

預處理 cnt[digit] 統計每個數字出現次數。

轉移時，若 s[i] == s[i-1] 且 (mask & (1<<(i-1))) == 0（即前一個相同數字未被選），則跳過選 i，避免產生相同排列。

四、完整 AC 代碼
#include <bits/stdc++.h>
using namespace std;
const int MAXM = 1050; // 2^10
const int MAXD = 1005;
int f[MAXM][MAXD], cnt[10];
char s[15];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int d; scanf("%s%d", s, &d);
        int n = strlen(s);
        memset(cnt, 0, sizeof(cnt));
        for (int i = 0; i < n; ++i) cnt[s[i]-'0']++;

        memset(f, 0, sizeof(f));
        f[0][0] = 1;
        for (int mask = 0; mask < (1< 0 && s[i] == s[i-1] && !(mask & (1<<(i-1)))) continue;
                    int nmask = mask | (1<

五、複雜度

狀態數：2^n · d ≤ 1024 × 1000 = 1.02×10⁶
轉移：每狀態最多 n=10 次 → 約 10⁷ 操作，T=15 總計 1.5×10⁸，C++ O2 可過。
空間：f[1024][1000] ≈ 4 MB。


六、優化建議

用 short 或 int 視答案範圍而定（10! = 3.6M，int 足夠）。
預計算 digit[i] = s[i]-'0'、pow10[mask] 等加速。
若 d 較大可用 unordered_map 壓縮餘數維度，但本題  陣列最快。