C++(g++ 7.5.0) 解法, 执行用时: 286ms, 内存消耗: 27892K, 提交时间: 2022-08-13 11:25:50

#include<bits/stdc++.h>
using namespace std;
const int SIZE=1e5+10;
int L,R;
int dp[85][12][85][85],s[85][10];
int num[12];
int val(int pos,int sum,int mod,int x,bool flag)
{
    if(x<sum) return 0;
    if(!flag) return dp[x][pos+1][x-sum][(x-mod)%x];
    if(pos==-1) return (mod==0&&sum==x);
    int res=0;
    for(int d=0;d<=num[pos];d++)
    {
        bool e=(d==num[pos]);
        res+=val(pos-1,sum+d,(mod+(s[x][pos])*d)%x,x,e);
         
    }
    return res;
}
int Calc(int x)
{
    int len=0,res=0;
    while(x) num[len++]=x%10,x/=10;
    for(int i=1;i<=81;i++) res+=val(len-1,0,0,i,true);
    return res;
}
void pre()
{
    for(int i=1;i<=81;i++)
    {
        memset(dp[i],0,sizeof(dp[i]));
        dp[i][0][0][0]=1;
        s[i][0]=1%i;
        for(int j=1;j<=9;j++) s[i][j]=(s[i][j-1]*10)%i;
        for(int j=1;j<=9;j++)
        for(int k=0;k<=j*9;k++)
        for(int p=0;p<=i;p++)
        for(int q=0;q<=9&&k>=q;q++)
        {
            dp[i][j][k][p]+=dp[i][j-1][k-q][((p-s[i][j-1]*q)%i+i)%i];
        }
         
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    pre();
    while(cin>>L>>R) cout<<Calc(R)-Calc(L-1)<<endl;
    return 0;
}

C++14(g++5.4) 解法, 执行用时: 346ms, 内存消耗: 31876K, 提交时间: 2020-04-05 13:05:35

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int INF = 0x3f3f3f3f;
const int maxn = 2e5 + 10;
int L, R;
int a[11], len;
int dp[11][90][90][90], mod;
int DP(int pos, int sum, int mod, int rem, bool limit)
{
    if(pos < 0)
        return (sum == mod && rem == 0) ? 1 : 0;
    if(!limit && dp[pos][sum][mod][rem] != -1)
        return dp[pos][sum][mod][rem];
    int up = limit ? a[pos] : 9;
    int tot = 0;
    for(int i = 0; i <= up; i++)
        tot += DP(pos - 1, sum + i, mod, (rem * 10 + i) % mod, limit && i == up);
    if(!limit)
        dp[pos][sum][mod][rem] = tot;
    return tot;
}
int solve(int x)
{
    len = 0;
    while(x)
    {
        a[len++] = x % 10;
        x /= 10;
    }
    int tot = 0;
    for(int i = 1; i <= 9 * len; i++)
        tot += DP(len - 1, 0, i, 0, true);
    return tot;
}
int main()
{
    memset(dp, -1, sizeof(dp));
    while(~scanf("%d %d", &L, &R))
        printf("%d\n", solve(R) - solve(L-1));
	return 0;
}

C++ 解法, 执行用时: 371ms, 内存消耗: 31864K, 提交时间: 2022-02-07 10:10:56

#include<bits/stdc++.h>
using namespace std;
int L,R,a[11],len,f[11][90][90][90],mod;
int F(int pos,int sum,int mod,int rem,int limit){
    if(pos<0)return(sum==mod&&!rem)?1:0;
    if(!limit&&f[pos][sum][mod][rem]+1)return f[pos][sum][mod][rem];
    int up=limit?a[pos]:9,tot=0;
    for(int i=0;i<=up;i++)tot+=F(pos-1,sum+i,mod,(rem*10+i)%mod,limit&&i==up);
    if(!limit)f[pos][sum][mod][rem]=tot;
    return tot;
}
int solve(int x){
    len=0;
    while(x)a[len++]=x%10,x/=10;
    int tot=0;
    for(int i=1;i<=9*len;i++)tot+=F(len-1,0,i,0,1);
    return tot;
}
int main(){
    memset(f,-1,sizeof(f));
    while(cin>>L>>R)cout<<solve(R)-solve(L-1)<<"\n";
    return 0;
}