自动搬运

查看原文

来自洛谷，原作者为

	liangbowen 不能再摆了，，，

搬运于2025-08-24 22:05:10，当前版本为作者最后更新于2022-12-02 18:38:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

题目传送门！

更好的阅读体验？

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

前置知识：会做简单的 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}$，哭泣。

这里用一个很常见的 trick：矩阵加速优化 DP。

我们设一组矩阵 $\begin{pmatrix} dp_{i, 0} & dp_{i, 1} \end{pmatrix}$。

然后很容易根据状态转移方程列出关系式：

$$\begin{pmatrix} dp_{i, 0} & dp_{i, 1} \end{pmatrix} \times \begin{pmatrix} 0 & 1 \\ 1 & 1 \end{pmatrix} = \begin{pmatrix} dp_{i+1, 0} & dp_{i+1, 1} \end{pmatrix} $$

再根据矩阵跑快速幂就秒掉了这题。

同上面的，仍然是要初始化两个（具体看代码）。

时间复杂度 $O(\log n \times t^3)$，$t = 2$（矩阵大小）。

你会发现这东西很小很小，所以随便过。

代码

很轻松拿到 $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;
}

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