C++14(g++5.4) 解法, 执行用时: 111ms, 内存消耗: 52680K, 提交时间: 2019-04-09 15:40:49

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int t,a,b;
int dp[19][89][89][89];
int y[19];

int dfs(int len,int he,int jl,int mo,bool limit)
{
	if(jl>he)return 0;
	if(len==0)
	{
		if(jl==he&&mo==0)return 1;
		return 0;
	}
	if(!limit&&dp[len][he][jl][mo]!=-1)return dp[len][he][jl][mo];
	int ans=0;int maxx=limit?y[len]:9;
	for(int i=0;i<=maxx;i++)
	{
		ans+=dfs(len-1,he,jl+i,(mo*10+i)%he,limit&&i==maxx);
	}
	if(!limit)dp[len][he][jl][mo]=ans;
	return ans;
}

int solve(int x)
{
	int k=0;
	while(x)y[++k]=x%10,x/=10;
	int ans=0;
	for(int i=1;i<=81;i++)ans=ans+dfs(k,i,0,0,1);
	return ans;
}

int main()
{
	memset(dp,-1,sizeof(dp));
	cin>>t;
	for(int i=1;i<=t;i++)
	{
		cin>>a>>b;
		printf("Case %d: %d\n",i,solve(b)-solve(a-1));
	}
	return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 972ms, 内存消耗: 2412K, 提交时间: 2020-03-13 20:37:35

#include<iostream>
#include<cstdio>
#define N 165
#define ll long long
using namespace std;
int mod,tot,cnt,a[25],mark[2][25][N][N];
ll f[2][25][N][N];
ll dp(int p,int d,int s,int v)
{
	if(!d) return !s&&!v;
	if(mark[p][d][s][v]==tot) return f[p][d][s][v];
	mark[p][d][s][v]=tot;
	ll t=0;
	int i,l=max(0,s-(d-1)*9),r=min((p)?9:a[d],s);
	for(i=l;i<=r;i++)
	t+=dp(p|(i<a[d]),d-1,s-i,(v*10+i)%mod);
	return f[p][d][s][v]=t;
}
ll solve(ll x)
{
	ll t=0;
	for(cnt=0;x;x/=10)
	a[++cnt]=x%10;
	for(mod=1;mod<=cnt*9;mod++)
	{
	tot++;
	t+=dp(0,cnt,mod,0);
}
return t;
}
int main()
{
	int T;
	scanf("%d",&T);
	for(int ca=1;ca<=T;ca++)
	{
		ll x,y;
		scanf("%lld%lld",&x,&y);
		printf("Case %d: %lld\n",ca,solve(y)-solve(x-1));
	}
}