题解：P12284 [蓝桥杯 2024 国 Python A] 数字与留言

· · 题解

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

我们考虑 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;
}