企业官网建设流程全解析

本人还在DP初级阶段，第一次看到题目时没反应过来用DP，这道题用到的知识还是很多的，记录一下自己的学习过程。

题目如下：

密码学家小蓝受邀参加国际密码学研讨会，为此他设计了一种新型锁，巧妙地融合了数学的严谨性与密码学的安全性。这把锁包含 2025 个连续的数字格，每个格子需填入一个正整数，从而形成一个长度为 2025 的序列 {a1,a2,…,a2025}{a1​,a2​,…,a2025​}，其中 aiai​ 表示第 ii 个格子上的数字。

要想解锁，该序列需满足以下条件：任意两个相邻格子中的数字，其最小公倍数（LCM）均为 2025。即对于所有的 ii（1≤i≤20241≤i≤2024），需满足：LCM(ai,ai+1)=2025LCM(ai​,ai+1​)=2025现在，请你计算有多少个不同的序列能够解开这把锁。由于答案可能很大，你只需输出其对 109+7109+7 取余后的结果即可。

代码：

基础知识：最大公约数，最小公倍数代码：

def gys(a,b):

while b:

a,b=b,a%b

return a

def lcm(a,b):

return (a*b//gys(a,b))

用到了最小公倍数，就要知道2025的质因数，看看有多少个数符合最小公倍数是2025

2025=3的4次方*5的二次方

共有（1+4）*（1+2）=15个数符合

nums=[1，3，5，9，15,25,27,45,75,81,135,225,405,675,2025]

下面要看看那两个数可以相邻：

ok[[False]*size for _ in range(size)]

for i in range(size):

for j in range(size):

if (nums[i],nums[j])==2025:

ok[i][j]=True

计算一下符合条件的数量，及总序列数：

dp=[1]*size

#因为第一个位置就只有一种情况：第一个位置，没有前面的数，不需要匹配任何人。每个数字单独放在这里，就是 1 种合法方案。所以每个数字的初始值都是 1！

for i in range(2024):

for j in range(size):

for k in range(size):

new_dp[k]=(new_dp[k]+dp[j])%(10**9+7)

dp=new_dp

print(sum(dp)%(10**9+7))

全部代码：

MOD = 10**9 + 7 nums = [1,3,5,9,15,25,27,45,75,81,135,225,405,675,2025] size = len(nums) def gcd(a,b): while b: a,b=b,a%b return a def lcm(a,b): return a*b//gcd(a,b) ok=[[False]*size for _ in range(size)] for i in range(size): for j in range(size): if lcm(nums[i],nums[j])==2025: ok[i][j]= True dp = [1]*size for _ in range(2024): new_dp=[0]*size for j in range(size): for k in range(size): if ok[j][k]: new_dp[k]=(new_dp[k]+dp[j])%MOD dp=new_dp print(sum(dp) % MOD)