题解：P10986 [蓝桥杯 2023 国 Python A] 2023

· · 题解

二项式反演。

题目里有“恰好”的标志，套路的，我们可以将它转化为至多/至少后再容斥回来。

当我们已经确定 k 个 2023 固定在这个数中时，我们发现，剩余的 n-4k 个数就可以随便选——前提是不能有 2023。

也就是说，在剩余的数随便选时，我们可能会多选若干个 2023。

很容易想到这可以转化成“至少”的形式。

那么问题就转化成了两部分：

我们先来看第一部分。

当确定 k 个 2023 时，我们有 k+1 个空可以插入那些随便选的数字。

举个例子：

x2023x2023x2023x

其中 x 代表的是一堆随便选的数字。

这是个经典的隔板法，讲这些数字分到 k+1 个空的方案数为 ：

\binom{(p-4k)+(k+1)-1}{(k+1)-1}

又因为题目明示了我们前导零的合法，所以再乘上每个数都有的 0\sim 9 的 10 种方案数，即为随便选的数的方案。

第二部分，直接套公式即可。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn = 1e6 + 5, N = 5e5 + 5, mod = 998244353;
int qpow(int b, int p) {
    int res = 1;
    while (p) {
        if (p & 1) {
            res = res * b % mod;
        }
        b = b * b % mod;
        p >>= 1;
    }
    return res;
}

int n, k, fac[maxn], ifac[maxn], g[N];

inline void init() {
    fac[0] = 1;
    for (int i = 1; i <= N; i ++) {
        fac[i] = fac[i - 1] * i % mod;
    }
    ifac[N] = qpow(fac[N], mod - 2);
    for (int i = N - 1; ~i; i --) {
        ifac[i] = ifac[i + 1] * (i + 1) % mod;
    }
}

inline int C(int n, int m) {
    if (n < m || n < 0 || m < 0) {
        return 0;
    } else {
        return fac[n] * ifac[m] % mod * ifac[n - m] % mod;
    }
}
signed main() {
    cin >> n >> k, init();
    for(int m = k; m <= n / 4; m ++) {
        int p = n - 4 * m;
        g[m] = C(p + m, m) * qpow(10, p) % mod;
    }
    int ans = 0;
    for(int i = n / 4; i >= k; i --) {
        if(i - k & 1) ans = (ans - C(i, k) * g[i] % mod + mod) % mod;
        else ans = (ans + C(i, k) * g[i] % mod) % mod;
    }
    cout << ans << '\n';
    return 0;
}