E. Segment Sum

感觉是一道比较难的数位dp
数位dp的做法显然 单点在于那么多状态该怎么记录 我写了好久没写出来 看了别人的代码发现很妙
首先预处理出 10的幂次 这个不过多讲
cout<<(solve(b)-solve(a-1)+MOD)%MOD<<endl;
这个是数位dp的套路

#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll MOD = 998244353ll;
int cnt[20];
ll ppow[22];
ll a,b,k;
struct Point{
    ll x,y;//x代表符合条件的有几个，y代表对答案的贡献
}dp[20][1<<12][2];
Point dfs(ll len,ll state,bool limit,bool non_zero){
    if(len==0) return Point{
    1,0};//一个数字枚举完了 符合条件的++ 不再产生贡献（之前已经计算了）if(!limit&&dp[len][state][non_zero].y) return dp[len][state][non_zero];//记忆化Point ans = Point{
    0,0};//初始化ansint Max = limit?cnt[len]:9;//套路for(int i=0;i<=Max;++i){
    ll temp = state|((non_zero||i)<<i); //改变状态if(__builtin_popcountll(temp)>k) continue;//删掉错误的状态Point t = dfs(len-1,temp,limit&&i==Max,non_zero||i);//临时变量ans.x = (ans.x+t.x)%MOD;//符合条件的个数增加ans.y = (ans.y+t.y+1ll*i*ppow[len-1]%MOD*t.x%MOD)%MOD;//当前数位的贡献增加}return dp[len][state][non_zero]=ans;
}
ll solve(ll x){
    memset(dp,0,sizeof dp);memset(cnt,0,sizeof cnt);int len=0;while(x){
    cnt[++len]=x%10;x/=10;}return dfs(len,0,true,0).y;//最高位开始枚举 现在还没有任何数位上有数字 到达了最高位 有前导零zero=true non_zero = false
}
int main(){
    ppow[0]=1;for(int i=1;i<20;++i) ppow[i]=ppow[i-1]*10%MOD;ios::sync_with_stdio(0);cin>>a>>b>>k;cout<<(solve(b)-solve(a-1)+MOD)%MOD<<endl;return 0;	
}