统计含K个非零数字的整数

题意解析

考虑 $\bf{数位DP}$。

将数字 $n$ 转化为字符串 $s$ 定义 $f(i, cnt, isLim, isNum)$ 表示构造第 $i$ 位及其之后数位的合法方案数，其余参数含义为：

• $cnt$ 表示前面选择的非零数字的数量。
• $isLim$ 表示当前是否受到了 $n$ 的约束（注意要构造的数字不能超过 $n$）。若为真，则第 $i$ 位填入的数字至多为 $s[i]$，否则可以是 $9$。如果在受到约束的情况下填了 $s[i]$，那么后续填入的数字仍会受到 $n$ 的约束。例如 $n=1234$，那么 $i=0$ 填的是 $1$ 的话，$i=2$ 的这一位至多填 $2$。
• $isNum$ 表示 $i$ 前面的数位是否填了数字。若为假，则当前位可以跳过（不填数字），或者要填入的数字至少为 $1$；若为真，则要填入的数字可以从 $0$ 开始。例如
  $n=123$，在 $i=0$ 时跳过的话，相当于后面要构造的是一个 $99$ 以内的数字了，如果 $i=1$ 不跳过，那么相当于构造一个 $10$ 到 $99$ 的两位数，如果 $i=1$ 跳过，相当于构造的是一个 $9$ 以内的数字。

AC代码

#include <bits/stdc++.h>
using namespace std;

constexpr int MOD = 998244353;

constexpr int N = 100;
constexpr int K = 10;

string s;
int k, n;
int dp[N][K+1];

int dfs(int idx, int cnt, int isLim, int isNum) {
    if (idx == n) return cnt == k;
    if (!isLim and dp[idx][cnt] != -1)
        return dp[idx][cnt];
    int res = 0;
    if (isNum == false)
        res = (res + dfs(idx + 1, cnt, false, false)) % MOD;
    int lo = (isNum ? 0 : 1);
    int hi = (isLim ? s[idx] - '0' : 9);
    for (int d = lo; d <= hi; ++d)
        if (d == 0 or cnt + 1 <= k)
            res = (res + dfs(idx + 1, cnt + (d > 0), isLim and d == hi, true)) % MOD;
    return dp[idx][cnt] = res;
}

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int _; cin >> _;
    while (_--) {
        cin >> s >> k;
        n = s.size();
        memset(dp, -1, sizeof dp);
        cout << dfs(0, 0, true, false) << '\n';
    }
    return 0;
}

复杂度分析

对于每个 $Testcase$ 时间复杂度为：$\mathrm{O}(mKD)$，其中 $m$ 为 $s$ 的长度，即 $\mathrm{O}(\log{N})$；$D=10$。
由于每个状态只会计算一次，因此动态规划的时间复杂度 = 状态个数 $\times$ 单个状态的计算时间。
本题状态个数为 $\mathrm{O}(mK)$，单个状态的计算时间为 $\mathrm{O}(D)$，因此总的时间复杂度为 $\mathrm{O}(mDK)$。