BM求线性递推
// 题目来源：ACM-ICPC 2018 焦作赛区网络预赛
题意
God Water喜欢吃Meat, Fish 和 Chocolate，每个小时他会吃一种食物，但有些吃的顺序是危险/不高兴的。求在N小时内他的饮食方案有多少种不同组合。在连续三小时内这些组合是不可行的：
unhappy :
MMM FFF CCC
dangerous :
MCF FCM CMC CFC
思路1
设第 N 小时能吃的饮食方案数为 A[N]，根据连续三小时的可能组合，我们可以发现 A[N] 可以由 A[N-1] 和 A[N-2] 递推得到。由于相邻两小时的组合不是独立的，不能利用乘法计数原理。
用向量 a[N] = (MM, FM, CM, MF, FF, CF, MC, FC, CC) 记录 N 小时的最后两小时所吃的食物状态总的方案数，那么只需要找到矩阵 A，使得 a[N-1] · A = a[N]，那么就能用矩阵快速幂解决。
构造的矩阵如下：
\[
A = \begin{bmatrix} 011000000\\
000111000\\
000000101\\
111000000\\
000101000\\
000000011\\
110000000\\
000110000\\
000000110 \end{bmatrix}
\]
思路2
&emps; 使用杜教的BM模板，扔进8~10项，调用gao函数直接求 N 项结果。 时间复杂度与矩阵快速幂等同。
AC代码1
点击查看代码
```cpp
#include
#include
using namespace std;
const int mod = 1e9+7;
typedef long long ll;
struct Mat {
ll m[9][9];
ll tot;
Mat operator*(const Mat& a)const {
Mat res = {0};
for(int i=0;i<9;i++) {
for(int j=0;j<9;j++) {
for(int k=0;k<9;k++) {
res.m[i][j] += m[i][k] * a.m[k][j] % mod;
res.m[i][j] %= mod;
}
res.tot =(res.tot + res.m[i][j]) % mod;
}
}
return res;
}
ll getSum() const {
return tot;
// ll res = 0;
// for(int i=0;i<9;i++)
// for(int j=0;j<9;j++)
// res = (res + m[i][j]) % mod;
// return res;
}
void print() const {
for(int i=0;i<9;i++) {
for(int j=0;j<9;j++) {
printf("%lld ", m[i][j]);
}
printf("\n");
}
}
};
Mat getI() {
Mat I = {0};
for(int i=0;i<9;i++)
I.m[i][i] = 1;
return I;
}
const Mat I = getI();
Mat getA0() {
Mat res = {0};
for(int k=0;k<3;k++)
for(int i=0;i<3;i++) {
for(int j=3*i;j<3*i+3;j++)
res.m[k*3+i][j] = 1;
}
res.m[0][0] = 0;
res.m[2][7] = 0;
res.m[4][4] = 0;
res.m[5][6] = 0;
res.m[6][2] = 0;
res.m[7][5] = 0;
res.m[8][8] = 0;
res.tot = 20;
return res;
}
const Mat A0 = getA0();
Mat pow_mod(Mat a, ll n) {
Mat res = I;
while(n) {
if(n&1) res = res*a;
a = a*a;
n >>= 1;
}
return res;
}
ll solve(ll n) {
if(n==1) return 3;
else if(n==2) return 9;
return pow_mod(A0, n-2).getSum();
}
int main() {
int T; cin>>T;
while(T--) {
ll n;
scanf("%lld", &n);
printf("%lld\n", solve(n));
}
return 0;
}
/*
MFC
3*3*3 = 27
unhappy:
MMM
FFF
CCC
dangerous:
MCF
FCM
CMC
CFC
M F C
MM 0 1 1
MF 1 1 1
MC 1 0 1
FM 1 1 1
FF 1 0 1
FC 0 1 1
CM 1 1 0
CF 1 1 0
CC 1 1 0
*/
```
AC代码2