P4910 题解

标签：int 题解 位填 ans mod include dp P4910

前言

题目传送门！

更好的阅读体验？

矩阵快速幂优化 DP 经典题。

题目简述

给定一个长度为 \(n\) 的环，每个位置可以填 \(1\) 或 \(2\)。相邻两个不能同时填 \(1\)。

求方案数。多测。

朴素 DP

思路

看到题目，很容易想到环形 DP。

设 \(dp_{i, 0}\) 表示第 \(i\) 位填 \(1\) 的总方案数，\(dp_{i, 1}\) 表示第 \(i\) 位填 \(2\) 的总方案数。

状态转移方程如下：

• 第 \(i\) 位填 \(1\)，则上一位只能填 \(2\)。所以 \(dp_{i, 0} = dp_{i - 1, 1}\)。
• 第 \(i\) 位填 \(2\)，则上一位可以填 \(1\) 或 \(2\)。所以 \(dp_{i, 1} = dp_{i - 1, 0} + dp_{i - 1, 1}\)。

初始化要分类讨论一下：

• 如果第 \(1\) 位填 \(1\)，则第 \(n\) 位只能填 \(2\)。所以答案算上 \(dp_{n, 1}\)。
• 如果第 \(1\) 位填 \(2\)，则第 \(n\) 位可以填 \(1\) 或 \(2\)。所以答案算上 \(dp_{n, 0} + dp_{n, 1}\)。

把公式抄上去即可。时间复杂度 \(O(n)\)。

代码

按照题目的应该是可以拿 \(60\) 分的。但是只有 \(48\) 分。

提交记录。

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7;
int n, dp[N][2]; //dp[i][0/1] : 第i位填A或B
void calc()
{
	for (int i = 2; i <= n; i++)
		dp[i][0] = dp[i - 1][1],                        //第i位填1，则上一位只能填2
		dp[i][1] = (dp[i - 1][0] + dp[i - 1][1]) % mod; //第i位填2，则上一位可以填1或2
}
void solve()
{
	long long ans = 0;
	scanf("%d", &n);

	dp[1][0] = 1, dp[1][1] = 0;           //第一位填1，
	calc(), ans = (ans + dp[n][1]) % mod; //则最后一位只能填2

	dp[1][0] = 0, dp[1][1] = 1;                      //第一位填2，
	calc(), ans = (ans + dp[n][0] + dp[n][1]) % mod; //则最后一位可以填1或2

	cout << ans << '\n';
}
int main()
{
	ios::sync_with_stdio(false);
	int T;
	scanf("%d", &T);
	while (T--) solve();
	return 0;
}

矩阵快速幂优化

思路

如果 \(n\) 就 \(10^6\)，那顶多一道黄题。但是 \(n\) 是 \(10^{18}\)，哭泣。

代码

很轻松拿到 \(100\) 分。跑得飞快，最慢的点 \(4\) 毫秒。

提交记录。

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;

const int N = 2, mod = 1e9 + 7;
namespace martix {
	void mul(int ANS[][N], int x[][N], int y[][N])
	{
		int ans[N][N] = {};
		for (int i = 0; i < N; i++)
			for (int j = 0; j < N; j++)
				for (int k = 0; k < N; k++)
					ans[i][j] = (ans[i][j] + 1ll * x[i][k] * y[k][j]) % mod;
		memcpy(ANS, ans, sizeof ans);
	}
	void ksm(int f[][N], int A[][N], long long y)
	{
		while (y)
		{
			if (y & 1) mul(f, f, A);
			mul(A, A, A);
			y >>= 1;
		}
	}
}; using namespace martix;

void solve()
{
	long long n, ans = 0;
	cin >> n;
	int zltAK[N][N] = {1, 0}; //第一位填1 的 初始矩阵
	int ioi[N][N] = {
		0, 1, 
		1, 1
	};
	ksm(zltAK, ioi, n - 1), ans = (ans + zltAK[0][1]) % mod; //则最后一位只能填2

	int hxyAK[N][N] = {0, 1}; //第一位填2 的 初始矩阵
	int csp[N][N] = {
		0, 1, 
		1, 1
	};
	ksm(hxyAK, csp, n - 1), ans = (ans + hxyAK[0][0] + hxyAK[0][1]) % mod; //则最后一位可以填1或2

	cout << ans << '\n';
}
int main()
{
	int T;
	scanf("%d", &T);
	while (T--) solve();
	return 0;
}

码字不易，希望能帮助到大家！

标签：int,题解,位填,ans,mod,include,dp,P4910
From： https://www.cnblogs.com/liangbowen/p/16945276.html