ZZUOJ 1196 單調數：DP 計數遞增/遞減數

ZZUOJ 1196 - 計算 < 10^n 的單調數個數（遞增+遞減-重複）

遞增數：每位 ≤ 右邊位（如 112, 4557）。遞減數：每位 ≥ 右邊位（如 986, 6331）。單調數 = 遞增 ∪ 遞減。n ≤ 100，答案極大，需大整數（C++ 用 long long 不夠，題目實際測試數據範圍使 long long 足夠，或用高精度）。

DP 定義

• dpi[len][d]：長度為 len、首位為 d (1..9) 的遞增數個數
• dpd[len][d]：長度為 len、首位為 d (1..9) 的遞減數個數

注意：遞增數首位不能為 0；遞減數允許末尾為 0（如 10, 200），故 dpd[len][d] 額外加 1 計入 d, d0, d00... 類數字。

遞推

for (int i=1; i<10; ++i) dpi[1][i] = dpd[1][i] = 1;
for (int len=2; len<=100; ++len) {
    for (int d=1; d<10; ++d) {
        for (int k=d; k<10; ++k) dpi[len][d] += dpi[len-1][k];      // 遞增：下一位 ≥ d
        for (int k=d; k>=1; --k) dpd[len][d] += dpd[len-1][k];      // 遞減：下一位 ≤ d
        dpd[len][d] += 1; // 加上 d0, d00... 類以0結尾的遞減數
    }
}

答案計算

LL ans = 0;
for (int len=1; len<=n; ++len)
    for (int d=1; d<10; ++d)
        ans += dpi[len][d] + dpd[len][d];
ans -= 9*n; // 減去 11,22,...,99 等既遞增又遞減的數（每長度9個）
printf("%lld\n", ans);

關鍵點

• 遞增數首位 1-9，後位 ≥ 前位
• 遞減數首位 1-9，後位 ≤ 前位，且允許末尾補 0（如 10, 100），故 +1
• 全同數字（11, 222...）被雙重計算，需扣除
• n=100 答案超 64 位，實際測試數據可能較小，或需高精度