自动搬运

查看原文

来自洛谷，原作者为

	fush 因为有了因为，所以有了所以，既然已成既然，何必再说何必。

搬运于2025-08-24 23:14:18，当前版本为作者最后更新于2025-04-23 13:06:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

除数不大，如果可以得到每个余数的数量，我们可以直接枚举两个余数，来统计最后的答案。

我们考虑 DP，$dp_{i,0/1,j}$ 表示考虑到第 $i$ 位，是否顶到 $x$，余数为 $j$ 的数量。

我们可以像数位 DP 一样，枚举每一位上的数字，以及上一位的余数就好了，记得去除 $0$。

最后统计答案的时候，三个数的余数是可以相同的，需要分类讨论。

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define FL(a,b,c) for(int a=(b),a##end=(c);a<=a##end;++a)
#define FR(a,b,c) for(int a=(b),a##end=(c);a>=a##end;--a)
#define lowbit(x) ((x)&-(x))
#define eb emplace_back
#define SZ(x) (int)((x).size())
#define int long long
#define vt vector
#define ar(x) array<int,x>
#define PII pair<int, int>
#define max(a, b)({auto f7r=(a);auto j3h=(b);f7r<j3h?j3h:f7r;})
#define cmax(a, b)({auto j3h=(b);(j3h>a)&&(a=j3h);})
#define min(a, b)({auto f7r=(a);auto j3h=(b);f7r>j3h?j3h:f7r;})
#define cmin(a, b)({auto j3h=(b);(j3h<a)&&(a=j3h);})
constexpr int N = 1e6 + 10, M = 2034, mod = 1e9 + 7;
int a[M], dp[20][2][M], lim[20], len;
int qpow(int a, int b = mod - 2, int ans = 1){
	for(;b;(a *= a) %= mod, b >>= 1)if(b & 1)(ans *= a) %= mod;
	return ans;
}
int32_t main(){
	cin.tie(0)->sync_with_stdio(0);
	int x, y, t, ans = 0, inv2 = qpow(2), inv6 = qpow(6);
	cin >> x >> y, t = x;
	while(t)lim[++len] = t % 10, t /= 10;

	dp[len + 1][1][0] = 1;
	FR(i, len, 1)  FL(j, 0, 2023)  FL(li, 0, 1)
		FL(k, 0, (t = (li ? lim[i] : 9)))  if(k != 2 && k != 4)
			(dp[i][li && (k == t)][(j * 10 + k) % 2024] += dp[i + 1][li][j]) %= mod;

	FL(i, 0, 2023)a[i] = dp[1][0][i] + dp[1][1][i];
	(a[0] += mod - 1) %= mod; //去除 0

#define C2(x) (x * (x - 1) % mod * inv2 % mod)
#define C3(x) (x * (x - 2) % mod * (x - 1) % mod * inv6 % mod)

	FL(i, 0, 2023)FL(j, i, 2023){
		int k = (y - (i + j) % 2024 + 2024) % 2024, z = ans;
		if(k < i || k < j)continue;
		if(i == j)
			if(j == k)ans += C3(a[i]);
			else ans += C2(a[i]) * a[k] % mod;
		else if(j == k)ans += C2(a[j]) * a[i] % mod;
		else if(i == k)ans += C2(a[i]) * a[j] % mod;
		else ans += a[i] * a[j] % mod * a[k] % mod;
		ans %= mod;
	}
	cout << ans;
	return 0;
}