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;
}