CF1073E Segment Sum 题解

题目链接：CF1073E Segment Sum

题意：

给定 \(l,r,k\) ，求 \([l,r]\) 有多少个数满足「不包含超过 \(k\) 个数码」，输出他们的和 \(\bmod {998244353}\) 。

\(0 \le k\le 10,~1\le l ,r \le 10^{18}\)

做了这题才发现自己对数位dp的掌握很烂

其实很水，用个状态 st 记录每个数码是否出现过

设 \(f_{i,j}\) 表示只考虑前 \(i\) 位（从低位向高位计数），数码状态为 \(j\) 的数字的个数

设 \(g_{i,j}\) 表示只考虑前 \(i\) 位（从低位向高位计数），数码状态为 \(j\) 的数字的和

则 \[ f_{i,j} = \sum f_{i-1,j^{\prime}}\\ \\g_{i,j} = \sum 10^{i-1} \times d \times f_{i-1,j^{\prime}} + g_{i,j^{\prime}} \] 其中 \(d\) 表示第 \(i-1\) 位要填啥， \(j^{\prime}\) 表示转移后的 \(j\) ，懒得讲，直接看代码（

注意考虑一下前导零什么的就好了（因为这里前导零会影响数码出现次数

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
#include <map>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
typedef pair<int,int> P;
#define F first
#define S second
const int p=998244353;
#define N (int)()

int l,r,k,num[25],pwd[25]; P f[25][(1<<10)+15];
int popc(int x){int c=0; while(x)x-=x&(-x),++c; return c;}
// int popc(int x){return __builtin_popcount(x);}
P dfs(int u,int st,bool limit,bool qd0)
{
    if(!u) return {popc(st) <= k,0};
    if((!limit) && (!qd0) && f[u][st].F!=-1)
        return f[u][st];
    P res={0,0},tmp; int up=limit?num[u]:9;
    for(int i=0,nx; i<=up; i++)
    {
        nx=(qd0 && (!i)) ? st : (st|(1<<i));
        tmp=dfs(u-1,nx,limit&&i==num[u],qd0&&i==0);
        res={(res.F+tmp.F)%p, (tmp.F*pwd[u-1]%p*i%p +res.S+tmp.S)%p};
    }
    if((!limit) && (!qd0)) f[u][st]=res;
    return res;
}
int solve(int x)
{
    int cnt=0;
    while(x){num[++cnt]=x%10,x/=10;}
    return dfs(cnt,0,1,1).S;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    memset(f,-1,sizeof(f)); pwd[0]=1;
    for(int i=1; i<=20; i++) pwd[i]=pwd[i-1]*10%p;
    cin >> l >> r >> k;
    cout << ((solve(r)-solve(l-1))%p+p)%p << '\n';
    return 0;
}