知识点: DP，矩阵加速
原题面
题目要求:
给定一个长度为 \(n\) 的环，要求在每个位置填入 金色或绿色，不能有两个相邻的绿色。
求填色方案数。
多组数据, \(T\le 10, n\le 10^{18}\)
分析题意
矩阵加速模板。
设 \(f_{i,0/1}\) 为当前填到第 \(i\) 位，第一个位置为 金色/绿色 的合法方案数。
分成第一个位置为 绿/金讨论：
- 第一个位置为绿色时，\(f_{1,0} = 0,f_{1,1} = 1\)。
由于不能有两个相邻的绿色，则结尾珠子必为金色。
其对答案的贡献为 \(f_{n,0}\) - 第一个位置为金色时，\(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}\)。
代码实现
//
/*
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;
}