Ural 1353: Milliard Vasya's Function - 位數和動態規劃解法

問題描述

Vasya 定義了一個名為「Vasya 函數」的數學函數：第 N 個 VF 在點 S 的值，等於從 1 到 N 之間、各位數字之和等於 S 的整數個數。題目要求計算當 N = 10^9（即十億）時，VF 在給定 S（1 ≤ S ≤ 81）處的值。

核心思路：數位動態規劃

由於 N 固定為 10^9，我們實際上是在統計 1 到 1,000,000,000 之間、位數和為 S 的數字個數。注意 10^9 本身是 10 位數（1 後跟 9 個 0），其位數和為 1，但題目範圍通常視為 1 到 10^9 - 1（即 9 位數）加上 10^9。不過標準解法是考慮最多 9 位數（因為 10^9 的位數和只有 1，單獨處理即可）。

定義 dp[i][j] 表示：長度為 i 位數（允許前導零）且各位數字和為 j 的數字個數。遞推關係：

• 最高位為 0 的情況：dp[i-1][j]（相當於在低位補 0）
• 最高位為 1~9 的情況：對於每個 k (1≤k≤9)，若 j≥k，則累加 dp[i-1][j-k]

初始條件：dp[1][1..9] = 1（一位數時，1~9 各自和為自身）。

代碼實現要點

預計算 dp[1..9][1..81]。輸入 S 後，若 S=1 輸出 10（包含 10^9 本身），否則將 1 到 9 位數符合條件的個數累加：sum = Σ dp[i][S] (i=1..9)。

複雜度分析

預計算 O(9 × 81 × 9) ≈ 6561 次操作，查詢 O(1)。記憶體極小，完全滿足 1 秒、64 MB 限制。

完整代碼

#include <cstdio>
#include <cstring>
using namespace std;

int dp[10][107];

int main() {
    memset(dp, 0, sizeof(dp));
    for (int i = 1; i <= 9; ++i) dp[1][i] = 1;
    for (int i = 2; i <= 9; ++i) {
        for (int j = 1; j <= 81; ++j) {
            dp[i][j] = dp[i-1][j]; // 最高位補 0
            for (int k = 1; k <= 9; ++k) {
                if (j > k) dp[i][j] += dp[i-1][j-k];
            }
        }
    }
    int S;
    while (scanf("%d", &S) != EOF) {
        if (S == 1) {
            printf("10\n"); // 包含 10^9
        } else {
            int sum = 0;
            for (int i = 1; i <= 9; ++i) sum += dp[i][S];
            printf("%d\n", sum);
        }
    }
    return 0;
}