主页
Featured image of post ACM练习——P4838 P哥破解密码……

ACM练习——P4838 P哥破解密码……

一言加载中_(:з」∠)_……

文章字数:1065
预计阅读时长: 分钟

题目链接

题目分析

  • 考点:矩阵动规……
    • 典例:斐波拉契数列……
  • 方法:矩阵快速幂……

标准动规思想,每个次序有三个决策,分别为选\(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+快速矩阵幂……

同时即便用基本的动规,个人实现方法中也有两个问题……

  1. 计算动规采用的递归,虽然思路好想,但容易栈溢出且更耗时……
    故应该在用递归方式想出dp思路后,再改用递推(顺推)来计算……
  2. 对于较少的询问,不必用表将计算出的解存储下来,直接计算即可……