第十五届蓝桥杯省赛PythonB组B题【数字串个数】题解（AC）

设 n = 10000 n = 10000 n=10000。

法一

1. 枚举 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。
2. 在长度为 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，乘积即为答案。

法二

1. 枚举 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。
2. 在长度为 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. 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

【在线测评】