题解 P4910 【帕秋莉的手环】
灵乌路空
2020-06-13 18:29:15
## 知识点: DP，矩阵加速
### [原题面](https://www.luogu.com.cn/problem/P4910)
### 题目要求:
>给定一个长度为 $n$ 的环，填入 金色或绿色。
>不能有两个相邻的绿色。
>多组数据, $T\le 10, n\le 10^{18}$
---
### 分析题意
矩阵加速模板。
设 $f_{i,0/1}$ 为当前填到第 $i$ 位，第一个位置为 金色/绿色 的合法方案数。
分成第一个位置为 绿/金讨论：
1. 第一个位置为绿色时，$f_{1,0} = 0,f_{1,1} = 1$。
由于不能有两个相邻的绿色，则结尾珠子必为金色。
其对答案的贡献为 $f_{n,0}$
2. 第一个位置为金色时，$f_{1,0} = 1, f_{1,1} = 0$。
此时结尾珠子颜色任意。
其对答案的贡献为 $f_{n,0} + f_{n,1}$
状态转移方程：
$f_{i,0} = f_{i-1,0} + f_{i-1,1}$
$f_{i,1} = f_{i-1,0}$
复杂度 $O(Tn)$，期望得分 $\text{60pts}$。
---
上式显然可矩阵加速，转移矩阵如下：
$$\begin{bmatrix}f_{i-1,0}&f_{i-1,1}\end{bmatrix} \times \begin{bmatrix}1&1\\1&0\end{bmatrix} = \begin{bmatrix}f_{i,0}&f_{i,1}\end{bmatrix}$$
复杂度 $O(T\log n)$，期望得分 $\text{100pts}$。
---
### 代码实现
```cpp
//
/*
By:Luckyblock
*/
#include <cstdio>
#include <ctype.h>
#include <cstring>
#include <algorithm>
#define ll long long
const ll kMod = 1e9 + 7;
//=============================================================
struct Matrix {
ll a[2][2];
} shift, sum;
ll T, n, ans; //0金 1绿
//=============================================================
inline ll read() {
ll f = 1, w = 0; char ch = getchar();
for (; !isdigit(ch); ch = getchar()) if (ch == '-') f = -1;
for (; isdigit(ch); ch = getchar()) w = (w << 3) + (w << 1) + (ch ^ '0');
return f * w;
}
Matrix operator * (const Matrix &a, const Matrix &b) {
Matrix c;
memset(c.a, 0, sizeof(c));
for (int k = 0; k <= 1; ++ k) {
for (int i = 0; i <= 1; ++ i) {
for (int j = 0; j <= 1; ++ j) {
c.a[i][j] = (c.a[i][j] + a.a[i][k] * b.a[k][j] % kMod) % kMod;
}
}
}
return c;
}
void Build(Matrix &a) {
memset(a.a, 0, sizeof(a.a));
for (int i = 0; i <= 1; ++ i) a.a[i][i] = 1;
}
Matrix qpow(Matrix x, ll y) {
Matrix ret;
Build(ret);
while (y) {
if (y & 1) ret = ret * x;
x = x * x; y >>= 1;
}
return ret;
}
//=============================================================
int main() {
T = read();
while (T --) {
n = read(), ans = 0;
memset(shift.a, 0, sizeof(shift.a));
shift.a[0][0] = shift.a[0][1] = shift.a[1][0] = 1;
shift = qpow(shift, n - 1);
memset(sum.a, 0, sizeof(sum.a));
sum.a[0][0] = 1, sum = sum * shift;
ans = ((ans + sum.a[0][0]) % kMod + sum.a[0][1]) % kMod;
memset(sum.a, 0, sizeof(sum.a));
sum.a[0][1] = 1, sum = sum * shift;
ans = (ans + sum.a[0][0]) % kMod;
printf("%lld\n", ans);
}
return 0;
}
```