[语言月赛 202403] 星云(Nebula Numbers) 题解

思路分析

位数不大于 $n$ 的正整数即 $[1, 10^n - 1]$。可以直接枚举 $[1, 10^n - 1]$ 统计数位和不超过 $k$ 的个数，也可以按数位 DP 递推 $n$ 位十进制数各数位和的方案数再减去全 $0$（数字 $0$ 不是正整数）。

参考代码

#include <algorithm>
#include <iostream>
using namespace std;

long long dp[10][105];

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, k;
    if (!(cin >> n >> k)) return 0;
    dp[0][0] = 1;
    for (int i = 1; i <= n; ++i)
    {
        for (int s = 0; s <= 70; ++s)
        {
            for (int d = 0; d <= 9; ++d)
            {
                if (s + d <= 100) dp[i][s + d] += dp[i - 1][s];
            }
        }
    }
    long long ans = 0;
    int lim = min(k, 100);
    for (int s = 1; s <= lim; ++s) ans += dp[n][s];
    cout << ans << "\n";
    return 0;
}