C++14(g++5.4) 解法, 执行用时: 355ms, 内存消耗: 239844K, 提交时间: 2018-08-05 14:04:57

#include<bits/stdc++.h>
using namespace std;
long long dp[13][133][133][133];//位数 要整除几 余几 已有几 
int a[13];
long long dfs(int len,int qi,bool f,int sum,int h,int tar){
	if(len==-1) {
		return sum==0&&h==tar;
	}
	if(!f&&dp[len][tar][sum][h]!=-1) return dp[len][tar][sum][h];
	int lim=f?a[len]:9;
	long long ret=0;
	for(int i=0;i<=lim;++i) {
		ret+=dfs(len-1,i,f&&i==lim,(sum*10+i)%tar,h+i,tar);
	}
	return !f?dp[len][tar][sum][h]=ret:ret;
}
int main(){
	int T,tot;
	long long n;
	memset(dp,-1,sizeof(dp));
	int cas=1;
	for(scanf("%d",&T);T--;){
		scanf("%lld",&n);
		tot=0;
		while(n){
			a[tot++]=n%10;
			n/=10;
		}
		long long ans=0;
		for(int i=1;i<=110;++i) ans+=dfs(tot-1,0,1,0,0,i);
		printf("Case %d: %lld\n",cas++,ans);
	}
}

C++11(clang++ 3.9) 解法, 执行用时: 278ms, 内存消耗: 239684K, 提交时间: 2020-10-17 08:39:54

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll dp[13][133][133][133];//位数 要整除几 余几 已有几
int a[13];
ll dfs(int len,int qi,bool f,int sum,int h,int tar) {
	if(len==-1) {
		return sum==0&&h==tar;
	}
	if(!f&&dp[len][tar][sum][h]!=-1) return dp[len][tar][sum][h];
	int lim=f?a[len]:9;
	ll ret=0;
	for(int i=0; i<=lim; ++i) {
		ret+=dfs(len-1,i,f&&i==lim,(sum*10+i)%tar,h+i,tar);
	}
	return !f?dp[len][tar][sum][h]=ret:ret;
}
int main() {
	int T,tot;
	ll n;
	memset(dp,-1,sizeof(dp));
	int cas=1;
	for(scanf("%d",&T); T--;) {
		scanf("%lld",&n);
		tot=0;
		while(n) {
			a[tot++]=n%10;
			n/=10;
		}
		ll ans=0;
		for(int i=1; i<=110; ++i) ans+=dfs(tot-1,0,1,0,0,i);
		printf("Case %d: %lld\n",cas++,ans);
	}
}