# CodeForces - 1073E ：Segment Sum （数位DP）

2021年09月15日 阅读数：2

You are given two integers c++

For example, if git

Input

The only line of the input contains three integers this

Output

Print one integer — the sum of numbers from atom

Examples
Input
10 50 2
Output
1230
Input
1 2345 10
Output
2750685
Input
101 154 2
Output
2189

（数位DP其实就是一棵树，子树相同的时候能够直接调用答案）orm

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define ll long long
#define pii pair<int,int>
#define mp make_pair
using namespace std;
const int Mod=998244353;
pii dp[20][1<<10],O=mp(0,0);
int v[20],num[1<<10],K,q[20],tot;
pii dfs(int pos,int st,int lim)
{
if(!lim&&dp[pos][st]!=O) return dp[pos][st];
if(pos==1) return mp(0,1);
int up=9; pii res=O,tmp; if(lim) up=q[pos-1];
rep(i,0,up){
if(num[st|(1<<i)]<=K){
tmp=dfs(pos-1,st|(1<<i),lim&&i==up);
(res.second+=tmp.second)%=Mod;
(res.first+=tmp.first)%=Mod;
(res.first+=(ll)v[pos-1]*i%Mod*tmp.second%Mod)%=Mod;
}
}
return dp[pos][st]=res;
}
int cal(ll x)
{
if(x==0) return 0;
tot=0; int ans=0;
while(x) q[++tot]=x%10,x/=10;
memset(dp,0,sizeof(dp));
rep(i,1,tot){
ll up=9; if(i==tot) up=q[tot];
rep(j,1,up){
pii tmp=dfs(i,1<<j,(i==tot)&&(j==q[tot]));
(ans+=(ll)v[i]*j%Mod*tmp.second%Mod)%=Mod;
(ans+=tmp.first)%=Mod;
}
}
return ans;
}
int main()
{
rep(i,1,1<<10) num[i]=num[i>>1]+(i&1);
v[1]=1; rep(i,2,18) v[i]=(ll)v[i-1]*10%Mod;
ll L,R; scanf("%lld%lld%d",&L,&R,&K);
printf("%d\n",((cal(R)-cal(L-1))%Mod+Mod)%Mod);
return 0;
}