首页 > Python资料 博客日记
第十五届蓝桥杯省赛PythonB组B题【数字串个数】题解(AC)
2024-05-11 12:00:04Python资料围观107次
Python资料网推荐第十五届蓝桥杯省赛PythonB组B题【数字串个数】题解(AC)这篇文章给大家,欢迎收藏Python资料网享受知识的乐趣
设 n = 10000 n = 10000 n=10000。
法一
- 枚举 3 3 3 的个数以及 7 7 7 的个数,假设 3 3 3 的个数为 i i i, 7 7 7 的个数为 j j j,那么非 3 , 7 3, 7 3,7 的个数即为 n − i − j n - i - j n−i−j。
- 在长度为 n n n 的字符串中选取 i i i 的方案数为 C n i C^i_n Cni,在剩余 n − i n - i n−i 个位置选取 j j j 个的方案数为 C n − i j C^j_{n - i} Cn−ij,剩余位置个数为 n − i − j n - i - j n−i−j,可选择的内容为 { 1 , 2 , 4 , 5 , 6 , 8 , 9 } \{1, 2, 4, 5, 6, 8, 9\} {1,2,4,5,6,8,9},共七个,故方案数为 7 n − i − j 7^{n - i - j} 7n−i−j,乘积即为答案。
法二
- 枚举 3 3 3 与 7 7 7 的个数之和,假设 3 3 3 与 7 7 7 的个数和为 i i i,那么非 3 , 7 3, 7 3,7 的个数即为 n − i n - i n−i。
- 在长度为 n n n 的字符串中选取 i i i 个的方案数为 C n i C^i_n Cni,在剩余 n − i n-i n−i 个位置选取非 3 , 7 3, 7 3,7 的方案数为 7 n − i 7^{n - i} 7n−i。
- 3 , 7 3, 7 3,7 的个数和为 i i i,假设题目无要求 3 , 7 3, 7 3,7 最少各为一个,那么每个位置有两种选择,故方案数为 2 i 2^i 2i,由于 2 i 2^i 2i 种方案中存在全 3 3 3 和全 7 7 7 的情况,所有有效方案数为 2 i − 2 2^i - 2 2i−2。
法一
MOD = int(1e9 + 7)
def qmi(a, b):
res = 1
while b > 0:
if b & 1:
res = res * a % MOD
a = a * a % MOD
b >>= 1
return res
n = 10000
N = int(1e4 + 10)
f = [[0 for i in range(N)] for i in range(N)]
def init():
for i in range(0, n + 1):
for j in range(0, i + 1):
if j == 0:
f[i][j] = 1
else:
f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % MOD
init()
res = 0
for i in range(1, n - 1 + 1):
for j in range(1, n - i + 1):
res = (res + f[n][i] * f[n - i][j] * qmi(7, n - i - j)) % MOD
print(res)
法二
MOD = int(1e9 + 7)
def qmi(a, b):
res = 1
while b > 0:
if b & 1:
res = res * a % MOD
a = a * a % MOD
b >>= 1
return res
n = 10000
N = int(1e4 + 10)
f = [[0 for i in range(N)] for i in range(N)]
def init():
for i in range(0, n + 1):
for j in range(0, i + 1):
if j == 0:
f[i][j] = 1
else:
f[i][j] = (f[i - 1][j] + f[i - 1][j - 1]) % MOD
init()
res = 0
for i in range(2, n + 1):
res = (res + f[n][i] * qmi(7, n - i) * (qmi(2, i) - 2)) % MOD
print(res)
运行结果:
157509472
版权声明:本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若内容造成侵权/违法违规/事实不符,请联系邮箱:jacktools123@163.com进行投诉反馈,一经查实,立即删除!
标签:
相关文章
最新发布
点击排行
- 版本匹配指南:Numpy版本和Python版本的对应关系
- Python 可视化 web 神器:streamlit、Gradio、dash、nicegui;低代码 Python Web 框架:PyWebIO
- 版本匹配指南:PyTorch版本、torchvision 版本和Python版本的对应关系
- 相关性分析——Pearson相关系数+热力图(附data和Python完整代码)
- Could not build wheels for llama-cpp-python, which is required to install pyproject.toml-based proj
- Python pyinstaller打包exe最完整教程
- Anaconda版本和Python版本对应关系(持续更新...)
- Python与PyTorch的版本对应