【蓝桥杯】24省赛:数字串个数
思路
本质是组合数学问题:
9个数字组成10000位数字有9**10000
可能
不包括3的可能8**10000
不包括7的可能8**10000
既不包括3也不包括77**10000
根据容斥原理:结果为
9
∗
∗
10000
−
8
∗
∗
10000
−
8
∗
∗
10000
+
7
∗
∗
10000
9**10000 - 8**10000 - 8**10000 + 7**10000
9∗∗10000−8∗∗10000−8∗∗10000+7∗∗10000
代码
这是道填空题,只需填入结果即可。但是直接运行会爆栈。需要快速幂优化。
!! 注意mod=int(1e9+7)
必须将浮点型转为整型,否则会出错。
import os
import sys
def ksm(a,n,mod):
if n==0:return 1
if n==1:return a
res = ksm(a,n//2,mod)
res = res*res % mod
if n%2==1:
res = res*a % mod
return res
mod = int(1e9+7)
# 10000
a = ksm(9,10000,mod)
b = ksm(8,10000,mod)
c = ksm(7,10000,mod)
# an = 9**10000 - 8**10000 - 8**10000 + 7**10000
an = (a - 2 * b + c) % mod
print(an)