当前位置：首页 > article >正文

【蓝桥杯】24省赛：数字串个数

article 2025/3/16 13:19:29

在这里插入图片描述

思路

本质是组合数学问题：
9个数字组成10000位数字有9**10000可能
不包括3的可能8**10000
不包括7的可能8**10000
既不包括3也不包括77**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)