POJ3070 | Fibonacci

Portal

矩阵加速递推,重点在于设计转移矩阵。画图分析:

(作图工具为 lydrainbowcat 同款 mspaint.exe)

可知转移矩阵为 [0111]\begin{bmatrix}0&1\1&1\end{bmatrix}

* 重载,按照矩阵乘法的方式运算。然后根据快速幂思想,乘偶数次 TT 等于乘 n2\frac{n}{2}T2T^2,最后复杂度为 O(logN)O(\log N)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <cstdio>
#include <cstring>
const int P=1e9+7;
struct mat {
int n,m,v[2][2];
mat() {memset(this,0,sizeof(mat));}
// int* operator [](cosnt int& p) {return v[p];} // 你猜我想干啥
mat operator *(const mat& B) const {
mat C;C.n=n,C.m=B.m;
for(int i=0;i<C.n;++i)
for(int j=0;j<C.m;++j)
for(int k=0;k<m;++k)
C.v[i][j]=(C.v[i][j]+1LL*v[i][k]*B.v[k][j]%P)%P;
return C;
}
}F,T;
void init() {
F.n=1,F.m=T.n=T.m=2;
F.v[0][1]=T.v[0][1]=T.v[1][0]=T.v[1][1]=1;
}
int main() {
init();
long long n;
scanf("%lld",&n);
for(;n;n>>=1) {
if(n&1) F=F*T;
T=T*T;
}
printf("%d",F.v[0][0]);
// printf("%d",F.v[0][1]);
return 0;
}

Download

本站所有原创内容采用 CC-BY-NC-ND 4.0 International 协议进行许可,附加条款亦可能应用。部分非原创内容版权为 上海アリス幻楽団黄昏フロンティア 等同人创作者所有。

题解 OI

评论

您需要成为穿墙的邪仙以加载 Disqus。