Classy Numbers

发表于 分类于 ，

    求范围[l,r]内数位上不超过3个非0数位的整数个数。

Classy Numbers

Created by LXC on Mon Oct 16 03:26:37 2023

https://codeforces.com/problemset/problem/1036/C

ranting: 1900

tag: combinatorics, dp

problem

求范围[l,r]内数位上不超过3个非0数位的整数个数。

solution

数位dp模板

对于n以内不超过3个非0数位的整数，定义dp[p][c][limit][zero]为 “填充到了第p位(p从0开始)，已出现的非0数字出现次数为c，limit为前i位是否为n的前缀，zero为前i位是否全部为0，第i位及之后的位数可以任意构造但是最终构造的数小于等于n且c不超过3” 的个数。

我们用两次数位dp，可以求出小于等于r的所有合法数目，以及小于等于l-1的所有合法数目。

二者相减则得到答案。

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55

#include <bits/stdc++.h>
// #define SINGLE_INPUT
#define ll long long
#define ull unsigned long long
#define N 500005
#define MOD 998244353
using namespace std;

string s;
ll dp[20][4][2][2];
ll dfs(int p, int c, int limit, int zero) {
    if (p == s.size()) return 1;
    if (dp[p][c][limit][zero] != -1) return dp[p][c][limit][zero]; //遇到计算过的状态直接返回
    ll res = 0;
    if (zero == 1) res += dfs(p+1, 0, 0, 1);

    for (int i=(zero?1:0); i<=(limit?s[p]-'0':9); i++) {
        if (i != 0 && c == 3) continue;
        res += dfs(p+1, c+(i != 0), limit&&(i==s[p]-'0'), 0);
    }
    return dp[p][c][limit][zero] = res;
}
ll countSpecialNumbers(ll n) {
    s = to_string(n);
    memset(dp, -1, sizeof(dp));
    return dfs(0, 0, 1, 1);
}

void sol() {
    ll l, r;
    cin >> l >> r;
    ll a = countSpecialNumbers(r);
    ll b = countSpecialNumbers(l-1);
    // cout << a << " " << b << endl;
    cout << a-b << "\n";
}

int main() {
    cout << setprecision(15) << fixed;
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}