Codeforces Round #157 Div.1 B：數位 DP 計數含 4/7 的數字

題目大意

給定 n，求有多少個不超過 n 的正整數，其十進制表示中恰好包含 k 個數字 4 或 7？其中 k 從 1 到 6（或更大），需對答案取模 1e9+7。實際題目可能要求計算某種組合數，但核心是數位 DP 統計「包含恰好 i 個 4/7 的數字個數」。

數位 DP 設計

定義 dfs(pos, cnt, tight)：處理到第 pos 位（從高到低），目前已有 cnt 個 4/7，tight 表示前綴是否已達上界。返回滿足條件的數字個數。

• 遞歸邊界：pos == 0 時，返回 cnt == target。
• 枚舉當前位數字 d（0~up），新 cnt = cnt + (d==4||d==7)。
• 記憶化：dp[pos][cnt] 在非 tight 狀態下可復用。

組合枚舉第二階段

得到 luck[i] = 包含恰好 i 個 4/7 的合法數字個數。然後需從中選 6 個數字（或其他固定數量），使其 4/7 總數滿足某條件（如

• 遞歸枚舉選第 1..6 個數字，每次從剩餘類型中選一個，乘以當前可選數量。
• 用 temp[i] 存儲 luck[i] + luck[i+1] + ... 作為剪枝或加速。

核心代碼片段

const int MOD = 1e9+7;
int dp[20][20], bit[20], luck[20], temp[20];

int dfs(int pos, int cnt, int target, bool tight) {
    if (pos == 0) return cnt == target;
    if (!tight && dp[pos][cnt] != -1) return dp[pos][cnt];
    int up = tight ? bit[pos] : 9;
    long long ans = 0;
    for (int d = 0; d <= up; d++) {
        int ncnt = cnt + (d==4 || d==7);
        ans += dfs(pos-1, ncnt, target, tight && d==up);
    }
    if (!tight) dp[pos][cnt] = ans % MOD;
    return ans % MOD;
}

long long dfs2(int left, long long ways, int maxType, int curSum, int maxFlag) {
    if (curSum >= maxFlag) return 0;
    if (left == 0) return ways * temp[curSum+1] % MOD;
    long long sum = 0;
    for (int i = 0; i <= maxType; i++) if (luck[i]) {
        luck[i]--;
        sum = (sum + dfs2(left-1, ways * luck[i] % MOD, maxType, curSum+i, maxFlag)) % MOD;
        luck[i]++;
    }
    return sum;
}

long long solve(int n) {
    if (n == 7) return 0; // 特殊情況
    int pos = 0, t = n;
    while (t) bit[++pos] = t%10, t/=10;
    memset(luck, 0, sizeof(luck));
    memset(temp, 0, sizeof(temp));
    for (int i = pos; i >= 0; i--) {
        memset(dp, -1, sizeof(dp));
        luck[i] = dfs(pos, 0, i, true);
        temp[i] = (temp[i+1] + luck[i]) % MOD;
    }
    luck[0]--; // 排除 0
    return dfs2(6, 1, pos, 0, luck[pos]?pos:pos-1) % MOD;
}

關鍵點總結

1. 數位 DP 統計「恰好 i 個 4/7」的數字個數 luck[i]。
2. 第二階段 DFS 枚舉選 6 個數字的組合，利用乘法原理累加方案數。
3. 注意模運算、邊界條件（如 n=7 特判）。
4. 複雜度：數位 DP O(位數 * 目標計數 * 10) ≈ O(20*10*10)；組合 DFS 狀態數極小。

總結

本題展示了「數位 DP + 組合枚舉」的兩階段解法：先用數位 DP 獲得各類別的計數，再用搜索/DP 組合這些計數得到最終答案。這是處理「數字屬性計數 + 組合選擇」類問題的通用框架。