题解：P11000 [蓝桥杯 2024 省 Python B] 数字串个数

· · 题解

题意

求长度为 10000 的不含 0 ，必须含 3 和 7 的数字串个数。

思路

这题只用到了灰常简单的容斥原理（因为只计算两个集合的并集）

首先，不考虑 3 和 7 ，每位可以选 1 到 9 ，一共有 9^{10000} 个数字串，再减去不含 3 和 7 的数量（不含 3 和不含 7 的并集）

根据容斥玄学公式：

|A_1 \cup A_2 \cup \ldots \cup A_n| =\sum_{i=1}^{n} |A_i| - \sum_{1 \leq i < j \leq n} |A_i \cap A_j| + \sum_{1 \leq i < j < k \leq n} |A_i \cap A_j \cap A_k| - \cdots + (-1)^{n+1} |A_1 \cap A_2 \cap \ldots \cap A_n|

这时，有人说：这神马东西？

上面是一般形式，两个集合的情况灰常简单：

|A \cup B| = |A| + |B| - |A \cap B|

所以，不含 3 和不含 7 的数字串数量为不含 3 的加不含 7 的再减去都不含的（多算了一次）

不含 3 和不含 7 的数字串都有 8^{10000} 个（每位只有 8 种），都不含的有 7^{10000} 个（除去 3 、 7 还有 7 种），所以答案为 (9^{10000} - 2 \times 8^{10000} + 7^{10000}) \bmod (10 ^ 9 + 7) = 157509472。

顺便说一句，这题为什么不能把字符串长度设成 10^{18} 什么的，快速幂都派不上用场。

代码

C++

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int P=1e9+7;
ll qpow(ll a,ll b){//QwQ快速幂
    ll res=1;
    while(b){
        if(b&1)res=res*a%P;
        a=a*a%P;
        b>>=1;
    }
    return res;
}
int main(){
    cout<<(qpow(9,10000)-2*qpow(8,10000)+qpow(7,10000))%P;
    return 0;
}
/*
#include<bits/stdc++.h>
using namespace std;
int main(){
    cout<<"157509472";
    return 0;
}
*/

python

print((9**10000-8**10000-8**10000+7**10000)%1000000007)
#print(157509472)

C++ AC 记录

python AC 记录