Codeforces 1073E(数位DP, 所有数和+状压DP)

Codeforces 1073E
题意:给你一个范围$[l,r]$,求其中数字数位上最多有$k$个不同的数的和。
这个数位DP如果求个数就比较容易,但是这里求和就比较麻烦。
先考虑求个数,设$dp(i,st)$为前$i$位的数的集合$st$的个数。注意前导零转移即可。
如果要求和,那么填完数对每个数位都要求一下对答案贡献。即如果填了第一位,那么后面填的可行个数将就是第一位上的填数贡献次数。以此类推。具体实现看代码。

知识点:
1、样例过不了难调,自己做小数据调

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<vector>
#include<set>
#include<queue>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long long
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
const LL MO = 998244353;
LL l, r, k, dp[20][1050], f[20][1050];
LL len, b[20], cf[30];
LL dfs(LL a, LL st, LL limit, LL p, LL &gx) {
if (a == 0ll) return gx = 1, 0;
if (p != -233 && !limit && dp[a][st] >= 0ll) return gx = f[a][st], dp[a][st];
LL cnt = 0ll;
for (LL i = 0ll; i <= 9ll; ++i) if (st & (1ll << i)) ++cnt;
LL ed = (limit ? b[a] : 9ll), ret = 0ll, hh = 0ll;
for (LL i = 0ll; i <= ed; ++i) {
LL whw = 0ll;
if (i == 0 && p == -233) ret = (ret + dfs(a - 1ll, st, (limit && (ed == i)), -233, whw)) % MO;
else if (st & (1ll << i)) ret = (ret + dfs(a - 1ll, st, (limit && (ed == i)), i, whw)) % MO;
else if (cnt < k) ret = (ret + dfs(a - 1ll, st | (1ll << i), (limit && (ed == i)), i, whw)) % MO;
ret = (ret + i * cf[a] % MO * whw % MO), hh = (hh + whw) % MO;
}
if (p != -233 && !limit) dp[a][st] = ret, f[a][st] = hh;
return gx = hh, ret;
}
LL getans(LL x) {
len = 0ll; while (x) b[++len] = x % 10ll, x /= 10ll;
ms(dp, -1ll);
return dfs(len, 0ll, 1ll, -233, len);
}
void clean() {
}
int solve() {
clean();
cf[1] = cf[0] = 1ll;
for (LL i = 2; i <= 21; ++i) cf[i] = (cf[i - 1] * 10ll) % MO;
scanf("%I64d%I64d%I64d", &l, &r, &k);
LL rans = getans(r), lans = getans(l - 1);
printf("%I64d\n", ((rans - lans) % MO + MO) % MO);
return 0;
}
}
int main() {
flyinthesky::solve();
return 0;
}

------ 本文结束 ------