萌新求助卡常
查看原帖
萌新求助卡常
795344
lfxxx_楼主2025/1/24 15:02
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=20;
int a[N];
int dig;
int dp[N][N*10][N*10][2];
int dfs(int u,int k,int s,int lim)
{
    if(k<0)
        return 0;
    if(!u)
        return !k&&!s;
    if(~dp[u][k][s][lim])
        return dp[u][k][s][lim];
    // cout<<u<<' '<<k<<' '<<s<<' '<<lim<<'\n';
    int ans=0;
    for(int i=0;i<=(lim?a[u]:9);++i)
        ans+=dfs(u-1,k-i,(s*10%dig+i)%dig,(lim&&i==a[u]));

    return dp[u][k][s][lim]=ans;
}
int calc(int n)
{
    int tot=0;
    while(n)
    {
        a[++tot]=n%10;
        n/=10;
    }
    int ans=0;
    for(int i=1;i<=N*10;++i)
    {
        dig=i;
        memset(dp,-1,sizeof dp);
        ans+=dfs(tot,i,0,1);
    }
    return ans;
}
signed main()
{
    int l,r;
    cin>>l>>r;
    cout<<calc(r)-calc(l-1);
}
2025/1/24 15:02
加载中...