HDU 4906 Our Happy Ending：狀壓 DP 滾動數組求方案數

HDU 4906 Our Happy Ending：狀壓 DP 滾動數組

給定 n 個數字，每個可選 0..l。選若干數使和為 k，求方案數模 1e9+7。n≤1000, k≤20, l≤10⁹。

狀態定義

狀態壓縮：用 k 位二進制數表示「能組成的和的集合」。第 i 位為 1 表示和 i 可達到。狀態數 2ᵏ (k≤20 → 1M 狀態，需優化)。

優化觀察

l 很大時，選取值 1..l 中，超過 k 的值對達到和 k 無貢獻（只能作為「不選」或「選但不影響狀態」）。將 l 拆分：

• 小值 1..k：需狀態轉移。
• 大值 k+1..l：選擇後狀態不變，只乘以方案數 (l-k)。

DP 轉移

dp[s] = 方案數使得可達和集合為 s
初始 dp[0] = 1
對每個數字：
  new_dp = dp * (l - k)  // 選大值的情況
  對每個狀態 s：
    對選值 v = 1..k：
      ns = s | (s << v) | (1 << (v-1))  // 新增和 v，並將原有和 + v
      new_dp[ns] += dp[s]
  dp = new_dp

完整代碼

const int MOD = 1000000007;
int dp[1<<20];
int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, k; long long l;
        scanf("%d%d%lld", &n, &k, &l);
        int S = 1 << k;
        long long big = l - k; if (big < 0) big = 0;
        memset(dp, 0, sizeof(dp));
        dp[0] = 1;
        while (n--) {
            for (int s=S-1; s>=0; s--) if (dp[s]) {
                long long val = dp[s];
                dp[s] = (dp[s] + val * (big % MOD)) % MOD; // 選大值
                for (int v=1; v<=k; v++) {
                    int ns = s | ((s << v) & (S-1)) | (1 << (v-1));
                    dp[ns] = (dp[ns] + val) % MOD;
                }
            }
        }
        long long ans = 0;
        for (int s=0; s