样例过不去求调
查看原帖
样例过不去求调
362750
TernaryTree楼主2022/7/15 18:01
#include <bits/stdc++.h>
#define int long long

using namespace std;

const int maxn = 2e2 + 1;

int dp[maxn][maxn][maxn];
int num[maxn], cnt, tot;

int dfs(int totsum, int curdig, int cursum, int curnum, bool lim) {
//	cout << curdig << " " << cursum << " " << curnum << endl;  
	if (curdig == 0) {
		return cursum == totsum && curnum == 0;
	}
	if (!lim && dp[curdig][cursum][curnum] != -1) {
		return dp[curdig][cursum][curnum];
	}
	int ans = 0;
	int to = (lim ? num[curdig] : 9); 
	for (int i = 0; i <= to; i++) {
		ans += dfs(totsum, curdig - 1, cursum + i, (curnum * 10 + i) % totsum, lim && i == to);
	}
	if (!lim) dp[curdig][cursum][curnum] = ans;
	return ans;
}

int solve(int x) {
	while (x) {
		num[++cnt] = x % 10;
		x /= 10;
	}
	int ans = 0;
	for (int i = 1; i <= 9 * cnt; i++) {
		memset(dp, -1, sizeof(dp));
		ans += dfs(i, cnt, 0, 0, 1);
//		cout << "*********************" << endl;
	}
	return ans;
}

signed main() {
	int l, r;
	cin >> l >> r;
	cout << solve(r) - solve(l - 1) << endl;
	return 0;
}
2022/7/15 18:01
加载中...