HDU 5389 Zero Escape：數位 DP 優化分組方案數

題目大意

• n 個人，每人 ID 為正整數。
• 兩門門檻值 `A`, `B`（1-9）。
• 將所有人分為兩組，各組 ID 的「數位根」（迭代求和至個位）分別等於 `A`, `B`。求分法數模 258280327。

關鍵觀察

• 數位根 `dr(x) = (x-1)%9 + 1`（x>0）。
• 設總數位根 `S = dr(Σ dr(id_i))`。
   若 `S == dr(A+B)`：兩組數位根和為 `A+B`，需 DP 計算方案數。
   否則：只能全部分在一組，答案 = `(S==A) + (S==B)`。

DP 方案數計算

dp[i][j]：前 `i` 人，第一組數位根為 `j` 的方案數。
轉移：`dp[i][j] = dp[i-1][j] + dp[i-1][(j - dr(id_i) + 9)%9]`。
空間優化：滾動數組 O(9)。
最終答案 = `dp[n][A] + dp[n][B]`（注意 `A==B` 時不重複）。

完整代碼

#include 
using namespace std;
const int MOD = 258280327;
int dr(int x) { return (x-1)%9 + 1; }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T; cin >> T;
    while (T--) {
        int n, A, B; cin >> n >> A >> B;
        vector a(n);
        int sum = 0;
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
            a[i] = dr(a[i]);
            sum += a[i];
        }
        sum = dr(sum);
        int target = dr(A + B);
        if (sum != target) {
            int ans = 0;
            if (sum == A) ++ans;
            if (sum == B) ++ans;
            cout << ans % MOD << "\n";
            continue;
        }
        vector dp(10), ndp(10);
        dp[a[0]] = 1;
        for (int i = 1; i < n; ++i) {
            fill(ndp.begin(), ndp.end(), 0);
            for (int j = 1; j <= 9; ++j) {
                int k = (j - a[i] + 9) % 9; if (k == 0) k = 9;
                ndp[j] = (dp[j] + dp[k]) % MOD;
            }
            dp.swap(ndp);
        }
        int ans = (dp[A] + dp[B]) % MOD;
        cout << ans << "\n";
    }
    return 0;
}

複雜度

• 每測試用例 O(n × 9)，n ≤ 1e5 極快。
• 空間 O(1)。