思路:
数位dp
我们平时做的数位dp都是求满足条件的数的个数, 这里要求满足条件的数的和
只要在原来的基础上求每一位的贡献就可以了,所以传参数时要传两个
代码:
#pragma GCC optimize(2) #pragma GCC optimize(3) #pragma GCC optimize(4) #include<bits/stdc++.h> using namespace std; #define fi first #define se second #define pi acos(-1.0) #define LL long long //#define mp make_pair #define pb push_back #define ls rt<<1, l, m #define rs rt<<1|1, m+1, r #define ULL unsigned LL #define pll pair<LL, LL> #define pli pair<LL, int> #define pii pair<int, int> #define piii pair<pii, int> #define mem(a, b) memset(a, b, sizeof(a)) #define fio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0); #define fopen freopen("in.txt", "r", stdin);freopen("out.txt", "w", stout); //head const int MOD = 998244353; int k; pll dp[20][1025]; int a[20], tot; LL pw[20]; pll dfs(int pos, int s, bool zero, bool limit) { if(!pos) return {__builtin_popcount(s) <= k, 0}; if(!limit && !zero && ~dp[pos][s].fi) return dp[pos][s]; int up = 9; if(limit) up = a[pos]; pll ans = {0, 0}; for (int i = 0; i <= up; i++) { pll res; if(zero && i == 0) res = dfs(pos-1, s, zero, limit&&i==up); else res = dfs(pos-1, s|(1<<i), zero&&i==0, limit&&i==up); (ans.fi = ans.fi + res.fi) %= MOD; (ans.se = ans.se + res.se + i*res.fi%MOD*pw[pos-1]%MOD) %= MOD; } if(!limit && !zero) dp[pos][s] = ans; return ans; } void init() { pw[0] = 1; for (int i = 1; i < 20; i++) pw[i] = (pw[i-1] * 10) % MOD; for (int i = 0; i < 20; i++) for (int j = 0; j < 1025; j++) dp[i][j].fi = dp[i][j].se = -1; } LL solve(LL n) { tot = 0; init(); while(n) { a[++tot] = n % 10; n /= 10; } return dfs(tot, 0, 1, 1).se; } int main() { LL l, r; scanf("%lld %lld %d", &l, &r, &k); printf("%lld ", (solve(r) - solve(l-1) + MOD) % MOD); return 0; }