这种题目还~
by wwz20050323 @ 2018-10-02 17:47:01
@[Steve_braveman](/space/show?uid=96570)
by 正式AFO @ 2018-10-02 17:51:57
这题递推或递归嘛。
by 正式AFO @ 2018-10-02 17:52:27
@[5743377_2002](/space/show?uid=36701) 可以，您强（逃。。
by Juanzhang @ 2018-10-02 18:00:05
您们先看看题面？
by Juanzhang @ 2018-10-02 18:00:32
@[Steve_braveman](/space/show?uid=96570) 您qp的时候res要初始化成$\mathbf{E_2}$吧？
by Juanzhang @ 2018-10-02 18:03:11
取模 %=mod
by olinr @ 2018-10-02 18:05:23
res要初始化为单位矩阵（对角线为1）
by olinr @ 2018-10-02 18:06:05
@[Steve_braveman](/space/show?uid=96570)
不一定对,你可以试试
```cpp
#include<iostream>
#include<cstring>
#define MOD 1000000007
using namespace std;
struct Matrix {
int a[2][2];
};
Matrix mul(Matrix x,Matrix y) {
Matrix temp;
memset(temp.a,0,sizeof(temp.a));
for(int i=0; i<2; i++) {
for(int j=0; j<2; j++) {
for(int k=0; k<2; k++) {
temp.a[i][j]+=(x.a[i][k]*y.a[k][j])%MOD;
}
}
}
return temp;
}
Matrix qp(Matrix a,int n) {
Matrix res;
memset(res.a,0,sizeof(res.a));
res.a[0][0]=res.a[1][1]=1;
while(n) {
if(n&1)res=mul(res,a);
n>>=1;
a=mul(a,a);
}
return res;
}
int main() {
int n;
cin>>n;
Matrix f,k;
f.a[0][0]=1;
f.a[0][1]=1;
k.a[0][0]=0;
k.a[0][1]=1;
k.a[1][0]=1;
k.a[1][1]=1;
Matrix x=mul(f,qp(k,n-1));
cout<<x.a[0][0];
}
```
by x_angelkawaii_x @ 2018-10-02 18:06:11
@[Steve_braveman](/space/show?uid=96570) 这里
``` cpp
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7;
struct matrix {
ll a[2][2];
matrix() { memset(a, 0, sizeof a); }
} temp;
matrix mul(matrix x,matrix y) {
for(int i=0; i<2; i++) {
for(int j=0; j<2; j++) {
temp.a[i][j] = 0;
for(int k=0; k<2; k++) {
temp.a[i][j] = (temp.a[i][j] + x.a[i][k] * y.a[k][j]) % MOD;
}
}
}
return temp;
}
matrix qp(matrix a, ll k) {
matrix res;
res.a[0][0] = res.a[1][1] = 1;
for (; k; k >>= 1, a = mul(a, a)) {
if (k & 1) res = mul(res, a);
}
return res;
}
int main() {
ll n;
cin>>n;
if (n < 3) return puts("1"), 0;
matrix F;
F.a[0][0] = F.a[0][1] = F.a[1][0] = 1;
printf("%lld", qp(F, n - 1).a[0][0]);
return 0;
}
```
by Juanzhang @ 2018-10-02 18:09:15