CF1073E Segment Sum

제목

이것을 찍어 문제를 보다.

2. 해법

명백한 디지털 dpdpdp는 먼저 답안을 차분의 형식으로 바꿀 수 있다(두 접두사가 상감한다).dp[i][s]dp[i][s]dp[i][s]를 설정하면 ii위를 고려하여 이미 선택한 수의 상태가 sss인 방안의 수와 방안의 합(그래서 실현 과정에서 pa i r pair pair)을 사용했다. 여기서 디지털 dp dp dp의 작법에 주의하자. 우리는 상계와 전도 0 0에 도달했는지 고려해야 한다. 이 두 가지 상황을 고려할 때 폭력적으로 계산하고 기억하지 못한다.

#include 
#include 
#include 
using namespace std;
#define int long long
#define pii pair
const int p = 998244353;
int read()
{
     
	int x=0,f=1;char c;
	while((c=getchar())<'0' || c>'9') {
     if(c=='-') f=-1;}
	while(c>='0' && c<='9') {
     x=(x<<3)+(x<<1)+(c^48);c=getchar();}
	return x*f;
}
int n,a[20],l,r,k,pw[20];pii dp[20][1024];
pii dfs(int x,int s,int up,int zero)
{
     
    if(!x) return make_pair(__builtin_popcount(s)<=k,0);
    if(!up && !zero && ~dp[x][s].first) return dp[x][s];
    pii ans=pii(0,0);
    for(int i=0;i<=9;i++)
    {
     
        if(up && i>a[x]) break;
        int to=(zero && i==0)?s:(s|(1<<i));
        pii t=dfs(x-1,to,up&&i==a[x],zero&&i==0);
        ans=make_pair((ans.first+t.first)%p,(ans.second+t.second+i*pw[x-1]%p*t.first)%p);
    }
    if(!up && !zero) dp[x][s]=ans;
    return ans;
}
int cal(int x)
{
     
    n=0;
    while(x) a[++n]=x%10,x/=10;
    return dfs(n,0,1,1).second;
}
signed main()
{
     
    memset(dp,-1,sizeof dp);
    pw[0]=1;
    for(int i=1;i<=18;i++)
        pw[i]=pw[i-1]*10%p;
    l=read();r=read();k=read();
    printf("%lld
",(cal(r)-cal(l-1)+p)%p);
}