蓝桥杯 Python 组知识点容斥原理

容斥原理 

这张图初中或者高中数学课应该画过

也就是通过这个简单的例子引出容斥原理的公式

这张图的面积：s1 + s3+ s7 - 2 * s2 - 2 * s4 - 2 * s6 + 3 * s5

通过此引导出容斥原理公式

那么下面来一起看看题目

题目描述

给定 n,m 请求出所有 n 位十进制整数中有多少个数中恰好出现了 m 个 2023。

例如 00202312023是一个 11 位的出现了 2 个 2023 的十进制整数。

由于结果可能很大，请输出答案对 998,244,353 取模的结果。

输入格式

输入一行包含两个整数 n,m 用一个空格分隔。

输出格式

输出一行包含一个整数表示答案。

输入输出样例

输入 

5 1

输出

20

算法的题目可以一步步转换一步步拆解，正难则反

这道题是求“恰好”，应该不是直接能想到的吧，转换一下，先求出所有的。也就是至少有 k 个 2023 的组合总数，那么在根据容斥原理的公式算出答案即可

推导：求 >= k 也要有上限，上限很明显就是 n // 4 最多也就是这么多个 2023。定义 f(m) 为我们至少有（这里是至少哦，非常关键） m 个 2023 的组合数。首先总数变成了n - 4 * m ，然后就相当于x2023x2023x...   x 表示这里要填数字。这样有 m 个 2023 就说明有 m + 1 个位置要添数字，问题就转换成了 n - 4 * m 个小球装进 m + 1 个桶的总方案数

先看总结：

（这里就不推导了）

那这里我们的情景时第二种容器可装可不装,方案数为

基本上到这就结束了，套容斥原理的公式就行了，我直接给出了（很好推导的）

然后就是无聊的代码了，组合数的各种求法和容斥原理的代码写法我建议去 acwing 看y总的基础课，经典永流传么hh

代码

mod = 998244353

def qmi(m, k, p):
    res, t = 1, m
    while k:
        if k & 1:
            res = res * t % p
        t = t * t % p
        k >>= 1
    return res

def inv(x):
    return qmi(x, mod - 2, mod)

N = 100010
fact = [0] * N
infact = [0] * N
fact[0], infact[0] = 1, 1
for i in range(1, N):
    fact[i] = i * fact[i - 1] % mod
    infact[i] = inv(fact[i])

def C(A, B):
    if A < B or A < 0 or B < 0:
        return 0
    return fact[A] * infact[B] % mod * infact[A - B] % mod

def f(n, x):
    return qmi(10, n - 4 * x, mod) * C(n - 3 * x, x) % mod

# print(C(5, 2))
n, m = map(int, input().split())
ist, ed = m, n // 4
ans = 0
for i in range(ist, ed + 1):
    if (i - m) & 1:
        ans = (ans - C(i, m) * f(n, i) % mod + mod) % mod
    else:
        ans = (ans + C(i, m) * f(n, i) % mod) % mod
print(ans)