题解：P12830 [蓝桥杯 2025 国 B] 新型锁

Sunrise_up · 2025-06-18 18:06:27 · 题解

这道题目发现直接模拟不可行。

思路

我们发现最小公倍数，就马上想到分解质因数。

将 2025 进行分解质因数，得 2025=3^4\times 5^2。

那么我们得出：

所以将题目中的式子简化：

所以推出 a_i 和 a_{i+1} 的组合是有限的，且每一个位置的计算只依赖前一个，考虑动态规划。

状态定义

定义 dp_{i,0/1,0/1} 表示位置 i 的因子是否含有 3^4 和 5^2。

初始化

很明显，dp_{0,0,0}=dp_{0,1,0}=dp_{0,0,1}=dp_{0,1,1}=0，无需做任何变化。

转移方程

对于第 i 个位置，只有四种需要变化：

• dp_{i,0,0}

  此时，它的前一个数必须拥有 3^4 和 5^2，即状态 dp_{i-1,1,1}，但是它可以任意变化，对于因子 3，它可以选择 3^0\sim 3^3 共四种；对于因子 5，它可以选择 5^0\sim 3^1 共两种。则它符合的只有 4\times2=8 种。

  所以我们可以得出：

  dp_{i,0,0}=8dp_{i-1,1,1}
• dp_{i,0,1}

  此时，它的前一个数必须拥有 3^4，即状态 dp_{i-1,1,0} 和 dp_{i-1,1,1}，但是它还可以变化因子 5，它可以选择 5^0\sim 5^1 共两种。则它符合的只有 2 种。

  所以我们可以得出：

  dp_{i,0,1}=2(dp_{i-1,1,0}+dp_{i-1,1,1})
• dp_{i,1,0}

  同 dp_{i,0,1}，它的前一个数必须拥有 5^2，即状态 dp_{i-1,0,1} 和 dp_{i-1,1,1}，但是它还可以变化因子 3，它可以选择 3^0\sim 3^3 共四种。则它符合的只有 4 种。

  所以我们可以得出：

  dp_{i,1,0}=4(dp_{i-1,0,1}+dp_{i-1,1,1})
• dp_{i,1,1}

  此时它只有唯一一种可能，但是它的前一个数是任意的，即 i-1 的所有状态：

  dp_{i,1,1}=dp_{i-1,0,0}+dp_{i-1,0,1}+dp_{i-1,1,0}+dp_{i-1,1,1}

综上，我们得出状态转移方程：

结果

答案即为 dp_{2025,0,0}+dp_{2025,0,1}+dp_{2025,1,0}+dp_{2025,1,1}。

所以使用编程进行复杂的运算后，我们得出结果是 385787853。

代码

使用 C++：

#include<bits/stdc++.h>
using namespace std;
int main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cout<<385787853;
    return 0;
}

使用 python：

print(385787853)

求点赞 qwq！