Problem

https://www.luogu.org/problemnew/show/CF1073E

Solution

枚举出现的数的状态，进行数位 dp，则得到的数属于状态的子集。

再做一下容斥即可。

注意由于是要求数的和，因此和和方案数都要记录在 dp 里。

以及注意前导 0 不受约束。

Code

#include<bits/stdc++.h>
#define CLR(x, y) memset(x, y, sizeof(x))
#define BCNT(x) __builtin_popcount(x)
#define MOD (998244353ll)
typedef long long ll;
using namespace std;

template<typename T> inline void gn (T &x) {
    char ch=getchar(), pl=0; x=0;
    while(ch<'0' || ch>'9') {
        if(ch==-1) exit(0);
        pl=ch=='-', ch=getchar();
    }
    while(ch>='0' && ch<='9') x=x*10+ch-'0', ch=getchar(); x*=pl?-1:1;
}

const int N=20, G=1<<10;
int a[N], k;
struct tmp { ll a, b; } f[N][G];
char vis[N][G];
int p[N];
int g[G];

tmp dfs(int x, int g, int lim, int pre) {
    if(x==-1) return {0, 1};
    if(!lim && !pre && vis[x][g]) return f[x][g];
    int maxn=lim?a[x]:9;
    tmp ret={0, 0}, na;
    for(int i=0;i<=maxn;i++) if((g&(1<<i)) || (!i && pre)) {
        na=dfs(x-1, g, lim && i==maxn, pre && !i);
        ret.a+=na.a+na.b*p[x]%MOD*i%MOD, ret.a%=MOD;
        ret.b+=na.b, ret.b%=MOD;
    }
    if(!lim && !pre) vis[x][g]=1, f[x][g]=ret;
    return ret;
}

int solve(ll x) {
    CLR(vis, 0);
    int t=0;
    while(x) a[t++]=x%10, x/=10;
    int ret=0;
    for(int i=1;i<G;i++) {
        g[i]=dfs(t-1, i, 1, 1).a;
        for(int j=(i-1)&i;j;j=(j-1)&i) g[i]=(g[i]-g[j]+MOD)%MOD;
        if(BCNT(i)<=k)
            ret=(ret+g[i])%MOD;
    }
    return ret;
}

ll l, r;
int main() {
    p[0]=1;
    for(int i=1;i<N;i++) p[i]=1ll*10*p[i-1]%MOD;
    gn(l), gn(r), gn(k);
    printf("%d\n", (solve(r)-solve(l-1)+MOD)%MOD);
    return 0;
}

本文链接：https://pst.iorinn.moe/archives/sol-cf-1073e.html
许可： https://pst.iorinn.moe/license.html
若无特别说明，博客内的文章默认将采用 CC BY 4.0 许可协议 进行许可☆