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

· · 题解

P10986 [蓝桥杯 2023 国 Python A] 2023

看到恰好出现 m 个 2023，显然二项式反演，考虑如何求钦定出现 m 个 2023。下文中，g(m) 表示钦定出现 m 个 2023，f(m) 表示恰好出现 m 个 2023。

先考虑如何钦定出来。插板法，相当于有 m 个板子，n - 4m 个小球，钦定的方案数即为

\binom{n - 3m}{m}

接着，未钦定的数字任意，方案数为

10^{n - 4m}

于是

g(m) = 10^{n - 4m} \binom{n - 3m}{m}

接着套二项式反演公式，有

f(m) = \sum_{i = m}^{\frac{n}{4}} (-1)^{i - m} \binom{i}{m} g(i) 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MOD = 998244353;

struct AC{
    vector<ll> fac;
    vector<ll> invfac;

    ll qpow(ll a,ll b){
        ll res = 1;
        for(;b > 0;b >>= 1,a = (a * a) % MOD){
            if(b & 1) res = (res * a) % MOD;
        }
        return res;
    }
    ll inv(ll x){
        return qpow(x,MOD - 2);
    }
    AC(int n){
        fac.resize(n + 1);
        invfac.resize(n + 1);
        fac[0] = 1;
        for(int i = 1;i <= n;i++) fac[i] = (fac[i - 1] * i) % MOD;
        invfac[n] = inv(fac[n]);
        for(int i = n - 1;i >= 0;i--) invfac[i] = (invfac[i + 1] * (i + 1)) % MOD;
    }

    ll A(ll n,ll m){
        if(n < m || n < 0 || m < 0) return 0;
        return (fac[n] * invfac[n - m]) % MOD;
    }
    ll C(ll n,ll m){
        if(n < m || n < 0 || m < 0) return 0;
        return (fac[n] * invfac[n - m] % MOD * invfac[m]) % MOD;
    }
    ll Cmm(ll n,int m){
        if(n < m || n < 0 || m < 0) return 0;
        ll res = 1;
        n %= MOD;
        for(ll k = n;k >= n - m + 1;k--){
            res = res * k % MOD;
        }
        return res * invfac[m] % MOD;
    }
    ll Lucas(ll n,ll m){
        if(m == 0) return 1;
        return Lucas(n / MOD,m / MOD) * C(n % MOD,m % MOD) % MOD;
    }
};

int main(){
    cin.tie(0) -> sync_with_stdio(0);
    ll n,m;
    cin>>n>>m;
    AC ac(n);
    ll ans = 0;
    auto g = [&](ll x) -> ll {
        return ac.qpow(10,n - 4 * x) * ac.C(n - 3 * x,x) % MOD;
    };
    for(ll i = m;i <= n / 4;i++){
        ll con = ac.C(i,m) * g(i);
        ans = (ans + con * ((i - m) % 2 == 0 ? 1 : -1) + MOD) % MOD;
    }
    cout<<ans;
    return 0;
}