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

· · 题解

我们先做一下数位 dp，令 f_{i, j, k} 表示前 i 位构成的数字对 2024 取模的结果为 j，是否贴紧数位限制的方案数，注意特判一下当前构造的数位数值是否不是 2 和 4 即可，最终对于每个模 2024 余数为 j 的数的方案为 a_j = f_{l, j, 0} + f_{l, j, 1}，l 是数字长度。

接下来考虑如何统计答案。枚举前两个数模 2024 的余数 i, j，直接计算出最后一个数模 2024 的余数 k（注意，我们这里假定 i \le j \le k，这并不影响答案计数），然后乘法原理一下就行了。注意特判 i = j = k, i = j, j = k 这三种情况。

时间复杂度 O(V^2 + \log x\log V)。

参考代码：

#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#define int long long
using ll = long long;
using ull = unsigned long long;
using pii = std::pair<int, int>;
template<typename T> using vec = std::vector<T>;
using vi = vec<int>; using vvi = vec<vi>;
template<typename T> using min_heap = std::priority_queue<T, vec<T>, std::greater<T>>;
template<typename T> using max_heap = std::priority_queue<T>;
#define fr first
#define se second
#define all(x) (x).begin(),(x).end()
#define sz(x) ((int)(x).size())
#define For(i, a, b) for(int i = (a); i <= (b); ++i)
#define Rof(i, a, b) for(int i = (a); i >= (b); --i)
#define Loop(i, a, b, s) for(int i = (a); \
    ((s) > 0) ? (i <= (b)) : (i >= (b)); i += (s))
template<typename T> T chkmax(T& x, T y) { return (x < y) ? (x = y, y) : x; }
template<typename T> T chkmin(T& x, T y) { return (x > y) ? (x = y, y) : x; }
#if defined(ENABLE_FASTIO)
#else
struct FastIO {
    FastIO() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr), std::cout << std::fixed; }
} fio;
#endif
const int mod = 1e9 + 7;
inline void inc(int& x, int y) {
    if ((x += y) >= mod)
        x -= mod;
}
int32_t main() {
    int x, y;
    std::cin >> x >> y;
    int t = x;
    vi d;
    while (t > 0)
        d.emplace_back(t % 10),
        t /= 10;
    std::reverse(all(d));
    int l = sz(d);
    vec<vvi> dp(l + 1, vvi(2024, vi(2, 0)));
    dp[0][0][1] = 1;
    For(i, 0, l - 1) For(j, 0, 2023) For(t, 0, 1) {
        int lim = (t ? d[i] : 9);
        For(k, 0, lim) {
            if (k != 2 && k != 4) {
                inc(dp[i + 1][(j * 10 + k) % 2024][t && k == lim], dp[i][j][t]);
            }
        }
    }
#define f2(x) (x) * ((x) - 1) % mod * ((mod + 1) / 2) % mod 
#define f3(x) (x) * ((x) - 1) % mod * ((x) - 2) % mod * ((mod + 1) / 6) % mod
    For(i, 0, 2023) inc(dp[l][i][0], dp[l][i][1]);
    inc(dp[l][0][0], mod - 1);
    int ans = 0;
    For(i, 0, 2023) For(j, i, 2023) {
        int k = (y % 2024 - (i + j) % 2024 + 2024) % 2024;
        if (k < j) continue;
        if (i == j && j == k)
            inc(ans, f3(dp[l][i][0]));
        else if (i == j && j != k)
            inc(ans, f2(dp[l][i][0]) * dp[l][k][0] % mod);
        else if (i < j && j == k)
            inc(ans, f2(dp[l][j][0]) * dp[l][i][0] % mod);
        else if (i < j && j < k)
            inc(ans, dp[l][i][0] * dp[l][j][0] % mod * dp[l][k][0] % mod);
    }
    std::cout << ans << "\n";
    return 0;
}