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

· · 题解

[蓝桥杯 2023] 2023

题目分析

题目大意

给出两个正整数 n,m，求在 n 位十进制数中恰好有 m 个 2023 的数字个数，允许含有前导零。

题目思路

使用二项式反演将问题转化为计算至少出现 k 个 2023 的方案数，然后通过容斥原理得到恰好出现 m 个的方案数。

组合计数：

  1. 在 n 位中选出 k 个 2023 可以通过确定首位置的方式来确定 2023 的位置，则转化成在 n-3k 个数里选出 k 个数；
  2. 选出 k 个 2023，则剩余 n-4k 位，由于允许前导零存在，故每一位都可以填 0-9 的任何数字，故剩余项方案数为 10^{n-4k}。

综上所述，在 n 位十进制数中至少出现 k 个 2023 的方案数为 g(k)={n-3k\choose k}\times 10^{n-4k}。

也可以使用隔板法来得出：

  1. 有 k 个 2023 作为隔板，则有 k+1 个可摆放的位置；
  2. 有 n-4k 个“位”的自由位置。

使用隔板法：将 n-4k 个自由位置分配到 k+1 个位置上，相当于解方程：

x_1+x_2+x_3+......+x_{k+1}=n-4k,x_i \ge 0

令 y_i=x_i+1，则

y_1+y_2+y_3+......+y_{k+1}=n-4k+k+1,y_i \ge 1

相当于在 n-4k+k+1=n-3k+1 之间放 k 个隔板（形成 k+1 个间隙），因为 y_i \ge 1，所以有 n-3k 个可放隔板的间隙，所以方案数为 {n-3k\choose k}。

容斥原理：

令 A_i 为至少存在 i 个，B_i 为恰好存在 i 个，最多存在 n 个，容斥原理则为 A_1=B_1-B_2+B_3-B_4+......+(-1)^{n-1} \times B_n 也就是 A_1=\sum_{i=1}^{n} (-1)^{n-1} \times B_i。

二项式反演：

令：

则存在基本关系：

g(k)=\sum_{i=k}^{\lfloor n/4\rfloor} {i \choose k} \times f(i)

解释：若一个数字串实际有 i 个 2023（i \geq k），选择其中任意 k 个位置作为指定位置，则共有 \binom{i}{k} 种选择方式，因此 f(i) 会被计入 g(k) 中 \binom{i}{k} 次。

二项式反演定理：

f(n)=\sum_{i=0}^{n} {n \choose i} g(i)\Leftrightarrow g(n)=\sum_{i=0}^{n} (-1)^{n-i} {n \choose i} f(i)

变体：

f(n)=\sum_{i=n}^{m} {i \choose n} g(i)\Leftrightarrow g(n)=\sum_{i=n}^{m} (-1)^{i-n} {i \choose n} f(i)

故可得出：

f(k)=\sum_{i=k}^{\lfloor n/4\rfloor} (-1)^{i-k} {i\choose k} g(i)

其中，g(i) 的计算在上述组合计数中。

最终公式：

f(m)=\sum_{k=m}^{K} (-1)^{k-m} \times {k\choose m} \times g(k)

其中 K=\lfloor n/4\rfloor 即 n 位十进制数中最大的 2023 可能出现的个数，g(k)={n-3k\choose k}\times 10^{n-4k} 即 n 位十进制数中至少出现 k 个 2023 的数字个数。

知识总结

数学知识

  1. 二项式定理
  2. 二项式反演
  3. 容斥原理
  4. 组合数学概念、表示及公式
  5. 乘法原理
  6. 逆元概念
  7. 费马小定理
  8. 模运算公式

算法知识

  1. 快速幂求逆元
  2. 求组合数（阶乘与逆元）

算法实现

预处理：

  4. 使用快速幂求逆元

主函数循环：

  1. 遍历可能的 2023 的个数 k（从 m 到 \lfloor n/4 \rfloor）；
  2. 计算 g(k)={n-3k\choose k}\times 10^{n-4k}；
  3. 计算二项式系数 {k \choose m}；
  4. 根据容斥原理调整正反 (-1)^{k-m}；
  5. 累计到 ans 最终答案，注意：由于容斥原理会加会减，且模运算会改变数的实际大小，为防止出现负数，在模运算之前加上模数，ans=(ans+(long long)c_1*c_2*sign+mod)%mod。

时间复杂度 \mathcal{O}(n)，空间复杂度 \mathcal{O}(n)。

AC Code。

#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+10,mod = 998244353;
typedef long long ll;
int fact[N],infact[N],pow10[N];//fact[i]--i 的阶乘,infact[i]--i 的阶乘逆元,pow10[i]--10 的 i 次幂
int qmi(int a,int k)//快速幂求逆元
{
    int res=1;
    while (k)
    {
        if (k&1) res=(ll)res*a%mod;
        a=(ll)a*a%mod;
        k>>=1;
    }
    return res;
}
void init(int n)
{
    fact[0]=infact[0]=pow10[0]=1;//初始化
    for (int i=1;i<=n;i++)
    {
        fact[i]=(ll)fact[i-1]*i%mod;//阶乘计算
        pow10[i]=(ll)pow10[i-1]*10%mod;//10 的幂计算
    }
    infact[n]=qmi(fact[n],mod-2);
    for (int i=n-1;i>=1;i--)
        infact[i]=(ll)infact[i+1]*(i+1)%mod;//阶乘逆元计算
}
int main()
{
    int n,m,ans=0,sign=-1;
    scanf("%d%d",&n,&m);
    init(n);
    for (int i=m;i<=n/4;i++)
    {
        sign*=-1;
        int a=n-i*3;
        int c1=(ll)fact[a]*infact[i]%mod*infact[a-i]%mod*pow10[n-4*i]%mod;
        int c2=(ll)fact[i]*infact[m]%mod*infact[i-m]%mod;
        ans=(ans+(ll)c1*c2*sign+mod)%mod;//sign 有时为 -1,由于模运算,要加 mod,在模 mod,以防为负数
    }
    printf("%d",ans);
    return 0;
}
End。