题解 P1939 【【模板】矩阵加速（数列）】
ouuan
2018-07-11 22:57:21
看楼上dalao们都是用f[n],f[n+1],f[n+2]推f[n+1],f[n+2],f[n+3]，然而我是用f[n],f[n+1],f[n+2]推f[n+3],f[n+4],f[n+5]
（然而只是预处理了矩阵的三次方）
f[n+3]=f[n]+f[n+2]不用多说
f[n+4]=f[n+3]+f[n+1]=f[n]+f[n+2]+f[n+1]
f[n+5]=f[n+4]+f[n+2]=f[n]+f[n+1]+2*f[n+2]
因此用来计算的矩阵就是
| 1 | 0 | 1 |
| :----------: | :----------: | :----------: |
| 1 | 1 | 1 |
| 1 | 1 | 2 |
这样算的话貌似能快一个可以忽略不计的常数..
代码如下：
```
#include <iostream>
using namespace std;
const long long M=1000000007;
struct Matrix
{
long long a[3][3]={{0}};
Matrix(int type=0)
{
if (type==1) //初始化为上文所述的矩阵
{
a[0][0]=a[0][2]=a[1][0]=a[1][1]=a[1][2]=a[2][0]=a[2][1]=1;
a[2][2]=2;
}
if (type==2) //初始化为对角线为1的矩阵，即单位矩阵
{
a[0][0]=a[1][1]=a[2][2]=1;
}
}
Matrix operator*(Matrix& b)
{
Matrix out;
int i,j,k;
for (i=0;i<3;++i)
{
for (j=0;j<3;++j)
{
for (k=0;k<3;++k)
{
out.a[i][j]=(out.a[i][j]+this->a[i][k]*b.a[k][j])%M;
}
}
}
return out;
}
};
int main()
{
long long t,n,i;
cin>>t;
while (t--)
{
cin>>n;
Matrix f(1),ans(2);
for (i=62;i>=0;--i) //二进制版快速幂，个人比较喜欢，平常用递归的小伙伴们也可以学一学
{
ans=ans*ans;
if ((1ll<<i)&(n-1)/3) //注意计算的是矩阵的(n-1)/3次方
{
ans=ans*f;
}
}
cout<<(ans.a[(n-1)%3][0]+ans.a[(n-1)%3][1]+ans.a[(n-1)%3][2])%M<<endl; //输出的时候判断一下n处于向量中的哪个位置，即n%3是几
}
return 0;
}
```