学习笔记_25_03_18

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

题目描述

小蓝想要构造出一个长度为 $10000$ 的数字字符串，有以下要求：

1. 小蓝不喜欢数字 $0$，所以数字字符串中不可以出现 $0$；

2. 小蓝喜欢数字 $3$ 和 $7$，所以数字字符串中必须要有 $3$ 和 $7$ 这两个数字。

请问满足题意的数字字符串有多少个？这个数字会很大，你只需要输出其
对 $10^9 + 7$ 取余后的结果。

输入格式

无

输出格式

一行一个整数表示答案。

解决方案

这道题本质上还是一个数学问题，在排除0之后，一共有1-9九个数字，因此一个长度为10000的字符串目前一共有9^10000种组合可能。

如果这九个数字中没有3，九个数字变为八个数字，则一共有8^10000种组合可能。

同理，如果没有7，一共有8^10000种组合可能；如果既没有3又没有7，则一共有7^10000种组合可能

那就不难得出一个类似于下图的韦恩图：

根据容斥原理不难得出我们所要求的结果数为9^10000 - 8^10000 - 8^10000 + 7^10000。则题解代码为：

print((9**10000 - 8**10000*2 + 7**10000) // (10 ** 9 + 7))

但是这条语句突破了Python中的最大整数限制并因此报错，所以这里还想强调一下pow()函数的使用，可以避免类似的情况：

mod = 10**9 + 7
print((pow(9, 10000, mod) - 2 * pow(8, 10000, mod) + pow(7, 10000, mod)) % mod)
# pow()函数的第三个参数即为前两个参数的计算结果将要取模的模数

P10999 [蓝桥杯 2024 省 Python B] 穿越时空之门

题目描述

随着 $2024$ 年的钟声回荡，传说中的时空之门再次敞开。这扇门是一条神秘
的通道，它连接着二进制和四进制两个不同的数码领域，等待着勇者们的探索。
在二进制的领域里，勇者的力量被转换成了力量数值的二进制表示中各数
位之和。

在四进制的领域里，力量的转换规则相似，变成了力量数值的四进制表示中各数位之和。

穿越这扇时空之门的条件是严苛的：当且仅当勇者在二进制领域的力量等同于四进制领域的力量时，他才能够成功地穿越。

国王选定了小蓝作为领路人，带领着力量值从 $1$ 到 $2024$ 的勇者们踏上了这段探索未知的旅程。作为小蓝的助手，你的任务是帮助小蓝计算出，在这 $2024$ 位勇者中，有多少人符合穿越时空之门的条件。

输入格式

无

输出格式

一行一个整数表示答案。

解决方案

这道题的思路很简单，主要想记录的点在于如何进行任意进制间的转换。由于Python默认只提供了二、八、十和十六一共四种进制之间的转换函数，因此掌握辗转相除法的代码实现还是非常有比较的，特此记录。

def convert_to_base(num, base):
    if num == 0:
        return "0"
    digits = []
    while num:
        digits.append(int(num%base))
        num //= base
    digits = digits[::-1]

    return ''.join(str(x) for x in digits)


def main():
    count = 0
    for i in range(1, 2025):
        i_bin = bin(i)[2:]
        i_four = convert_to_base(i, 4)

        sum_bin = 0
        sum_four = 0
        for m in i_bin:
            sum_bin += int(m)
        for n in i_four:
            sum_four += int(n)

        if sum_bin == sum_four:
            count += 1

    print(count)

if __name__ == "__main__":
    main()