题目链接
P4838 P哥破解密码
题目分析
- 考点：矩阵动规……
- 典例：斐波拉契数列……
- 方法：矩阵快速幂……
标准动规思想，每个次序有三个决策，分别为选$1$个$A$，选$2$个$A$，选$B$……
$f[i][A_1] = f[i-1][B]$
$f[i][A_2] = f[i-1][A_1]$
$f[i][B] = f[i-1][A_1] + f[i-1][A_2] + f[i-1][B]$
最后输出：$f[n][A_1] + f[n][A_2] + f[n][B]$
但直接动规求会TLE，发现满足矩阵动规性质，则采用动规优化——矩阵动规……
矩阵动规讲解
个人代码
//P4838 [P哥破解密码](https://www.luogu.com.cn/problem/P4838)
#include <bits/stdc++.h>
//#define MAX 10000000 //dp中的状态存储图表最大大小（历史遗留垃圾x……
#define matrix_MAX 3
#define MOD 19260817
using namespace std;
struct typeMatrix
{
long long mat[matrix_MAX + 1][matrix_MAX + 1] = {};
int x, y;
typeMatrix(int x, int y) : x(x), y(y) {}
inline typeMatrix operator*(const typeMatrix &a) const //矩阵乘法实现//第一个const Type &a用来直接传地址并防止修改，节约空间；第二个const防止修改结构体内其他变量
{
typeMatrix res(x, a.y);
for (int i = 1; i <= x; i++) //矩阵a(x1,y1);b(x2,y2)，新矩阵为res(x1,y2)，做y1(或x2)次乘法累加
for (int j = 1; j <= a.y; j++)
for (int k = 1; k <= y; k++)
res.mat[i][j] = (res.mat[i][j] + mat[i][k] * a.mat[k][j]) % MOD; //就矩阵乘法
return res;
}
void initPowAns(int size)
{
for (int i = 1; i <= size; i++)
mat[i][i] = 1; //注意标准快速幂中初始化为令ans=1，换成矩阵中初始化为令主对角线为1……
}
inline typeMatrix operator^(int power) const //快速幂实现
{
typeMatrix ans(y, y), base = *this;
ans.initPowAns(y); //见上面分析：递推矩阵大小为y*y
while (power)
{
if (power & 1)
ans = ans * base;
base = base * base;
power >>= 1;
}
return ans;
}
} Matrix(2, 3), fx(3, 3); //Matrix状态矩阵，fx递推矩阵
int main()
{
int T, n;
Matrix.mat[1][1] = 1, Matrix.mat[1][3] = 1; //设置状态矩阵
fx.mat[1][2] = fx.mat[1][3] = fx.mat[2][3] = fx.mat[3][1] = fx.mat[3][3] = 1; //设置递推矩阵
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
typeMatrix ans = Matrix * (fx ^ (n - 1));
printf("%lld\n", (ans.mat[1][1] + ans.mat[1][2] + ans.mat[1][3]) % MOD);
}
}
附：初始代码——基础动规方法
struct dp
{
long long A_1, A_2, B;
} dp[MAX];
void init()
{
memset(dp, -1, sizeof(dp));
dp[1].A_1 = 1, dp[1].A_2 = 0, dp[1].B = 1;
}
long long dpSearch(int top, int cmd)
{
if (cmd == 1)
return (dp[top].A_1 != -1) ? dp[top].A_1 : dp[top].A_1 = dpSearch(top - 1, 3) % 19260817;
if (cmd == 2)
return (dp[top].A_2 != -1) ? dp[top].A_2 : dp[top].A_2 = dpSearch(top - 1, 1) % 19260817;
return (dp[top].B != -1) ? dp[top].B : dp[top].B = (dpSearch(top - 1, 1) + dpSearch(top - 1, 2) + dpSearch(top - 1, 3)) % 19260817;
}
int main()
{
int T, n;
init();
scanf("%d", &T);
while (T--)
{
scanf("%d", &n);
printf("%lld\n", (dpSearch(n, 1) + dpSearch(n, 2) + dpSearch(n, 3)) % 19260817);
}
return 0;
}
初始代码分析
最开始整体的动规思路是正确的，并且正确的求出了具体的状态转移方程……
但首先，动规从开始到结束直接求出来，是$O(n)$的复杂度，要TLE……
考虑动规的优化之一——矩阵DP+快速矩阵幂……
同时即便用基本的动规，个人实现方法中也有两个问题……
- 计算动规采用的递归，虽然思路好想，但容易栈溢出且更耗时……
故应该在用递归方式想出dp思路后，再改用递推（顺推）来计算…… - 对于较少的询问，不必用表将计算出的解存储下来，直接计算即可……