40pts 求助
查看原帖
40pts 求助
480300
_ROSE_楼主2022/7/16 15:54

AC #1#2#3#10,其余WA

/*
    Author: Rose
    Date & Time: 16/07/22 15:30
    LG P4127
*/
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;

#define ll long long
ll mod,len,a,b;
int num[25];
ll dp[25][205][205];

ll dfs(int now,int sum,bool lmt,ll pre){
    if(now>len) {
        if(sum==0) return 0;
        else return pre==0&&(sum==mod);
    }
    if(!lmt&&dp[now][sum][pre]!=-1) return dp[now][sum][pre];
    ll ans=0;
    int t=lmt?num[len-now+1]:9;
    for(int i=0;i<=t;i++){
        ans+=dfs(now+1,sum+i,(lmt&&i==t),(pre*10+i)%mod);
    }
    if(!lmt) dp[now][sum][pre]=ans;
    return ans;
}

ll f(int x){
    len=0;
    while(x){
        num[++len]=x%10;
        x/=10;
    }
    ll res=0;
    for(mod=1;mod<=9*len;mod++){
        memset(dp,-1,sizeof(dp));
        res+=dfs(1,0,1,0);
    }
    return res;
}
int main(){
    scanf("%lld%lld",&a,&b);
    printf("%lld",f(b)-f(a-1));
    return 0;
}
2022/7/16 15:54
加载中...