比赛 |
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;
}