比赛 2022级DP专题练习赛8 评测结果 AAAAAAAAAA
题目名称 同类分布 最终得分 100
用户昵称 zxhhh 运行时间 6.357 s
代码语言 C++ 内存使用 12.46 MiB
提交时间 2023-03-01 21:06:13
显示代码纯文本
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int N = 20, M = 210;

ll dp[N][M][M], a, b;
int mod, l, c[N];

ll dfs (int pos, int s, ll m, int limit) {
//	if(mod == 10) cout << dp[1][0][0] << endl; 
	if (!pos && !s) return 0;
	if (!pos) {
//		if (s == mod && mod == 10) cout << 11 << endl;
		return ((m == 0 && s == mod) ? 1 : 0);
	}
//	if (mod == 10) cout << pos << " " << s <<" " << m << " " <<limit << endl;
	if (!limit && dp[pos][s][m] != -1) {
//		if (mod == 10)cout << pos << " 114 " << s << " " << m << " " <<dp[pos][s][m] << endl; 
		return dp[pos][s][m];
	}
	ll res = 0; int mn = limit ? c[pos] : 9;
	for (int i = 0;i <= mn;i++) {
		res += dfs(pos - 1, s + i, (10ll * m + i) % mod, limit && (i == mn));
//		if (mod == 10 && dfs(pos - 1, s + i, (10ll * m + i) % mod, limit && (i == mn))) cout << pos-1 << " 111 " << s+i <<  " " << (10ll * m + i) % mod << " " << (int)(limit && (i == mn)) << " " << res << endl; 
		
	}
	return limit ? res : dp[pos][s][m] = res;
}

ll ans (ll x) {
	l = 0; 
	while(x) c[++l] = x % 10, x /= 10;
	int mv = l * 9; ll res = 0;
	for (mod = 1;mod <= mv;mod++) {
		memset(dp, -1, sizeof(dp));
		res += dfs(l, 0, 0, 1);
//		cout << mod << " " << dfs(l, 0, 0, 1) << endl;
	}
	return res;
}

int main () {
	freopen("self.in", "r", stdin);
	freopen("self.out", "w", stdout);
	cin >> a >> b;
	cout << ans(b) - ans (a - 1) << endl;
	return 0;
}