题解 P4910 【帕秋莉的手环】
灯芯糕
2018-10-06 16:56:34
## 矩阵快速幂解法：
这是一个类似斐波那契数列的矩乘快速幂，所以推荐大家先做一下下列题目：（会了，~~差不多就是多倍经验题了~~）
注：如果你不会矩阵乘法，可以了解一下[P3390](https://www.luogu.org/problemnew/show/P3390)的题解
[P1939 【模板】矩阵加速（数列）](https://www.luogu.org/problemnew/show/P1939)
[P3390 【模板】矩阵快速幂](https://www.luogu.org/problemnew/show/P3390)
[P1306 斐波那契公约数](https://www.luogu.org/problemnew/show/P1306)
[P1962 斐波那契数列](https://www.luogu.org/problemnew/show/P1962)
[P4838 P哥破解密码](https://www.luogu.org/problemnew/show/P4838)
由题意可得：相邻两个珠子中必有金属性珠子。这其实就可以理解为不能有连续的两个木属性珠子。这样一看，此题就和[P4838 P哥破解密码](https://www.luogu.org/problemnew/show/P4838)差不多了。只不过这题是个2*2矩阵乘法
### 进入正文：
我们先一次将1~n中每一个珠子的情况枚举
```cpp
// n=1 n=2 n=3 n=4 n=5 n=6 .......
//可放金属性珠子： 1 2 3 5 8 13 .......
//可放木属性珠子： 1 1 2 3 5 8 .......
```
不难发现这就是一个斐波那契数列的递推
### 但是：这是一个手环！
所以第一个珠子与最后一个手环是相连的，他们会互相影响！
不过他们只会影响对方而不会影响其他珠子，我们可以将第一颗珠子选金属性与木属性这两种情况分开：
```cpp
//第一颗珠子为金属性： 若 n=5
// 1 2 3 4 n .......
//金属性： 1 1 2 3 5 .......
//木属性： 0 1 1 2 3 .......
//第一颗珠子为木属性： n=5
// 1 2 3 4 n .......
//金属性： 0 1 1 2 3 .......
//木属性： 1 0 1 1 0 .......
//最后一颗不能为木!
//两种情况加起来就是样例1的解了
```
所以此题就是求斐波那契数列**第n项** 加 **第n-1项的两倍**
然后就可矩阵快速幂了！递推矩阵如下
```cpp
// 1 1
// 0 1
```
## 不过我们当然不能止步于此：
因为还有一种更无脑有效的方法：
既然矩阵可以快速幂，那么说明每两个递推数（即答案）之间的递推矩阵是一样的！
所以我们可以先手算两组结果，然后直接推出递推矩阵：
```cpp
// 3 4 乘 递推矩阵 = 4 7
// 解上述方程得递推矩阵为：
// 0 1
// 3 4 乘 = 4 7
// 1 1
```
## 下面上代码：
```cpp
#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007//简化一下
struct ju{
long long a[2][2];//不用long long只有8分哦（亲测QAQ）
ju operator *(const ju &x){
ju res;//这里需要另外建个矩阵存答案
memset(res.a,0,sizeof(res.a));
for(int i=0;i<2;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
res.a[i][j]=(res.a[i][j]+a[i][k]%mod*(x.a[k][j])%mod)%mod;
return res;
} //重载运算符，（可以写成函数）
}base,ans;//两个基本矩阵
int main(){
long long n,t;
scanf("%lld",&t);//只有t就不写快读了
while(t--){
scanf("%lld",&n);n--;//n要减一，不然会错 QAQ
base.a[0][0]=0;base.a[0][1]=1;base.a[1][0]=1;base.a[1][1]=1;
ans.a[0][0]=2;ans.a[0][1]=1;ans.a[1][0]=0;ans.a[1][1]=0;//初始化
while(n){//快速幂，（也可以写成函数）
if(n%2==1) ans=ans*base;
base=base*base;
n/=2;
}
printf("%lld\n",ans.a[0][1]%mod);
} //输出
return 0;
}
```
### 代码中ans的初始化已经是n=1时的答案了所以n要减一。
啊，写题解好累啊，是我太蒟了吗。。