题意
已知 F i b o n a c c i Fibonacci Fibonacci数列 f 1 = 1 , f 2 = 1 , f 3 = 2 , . . . . . , f n = f n ? 1 + f n ? 2 f_1=1,f_2=1,f_3=2,.....,f_n=f_{n-1}+f_{n-2} f1?=1,f2?=1,f3?=2,.....,fn?=fn?1?+fn?2?
输入 n n n和 m m m，求 f n f_n fn? m o d mod mod m m m.
**数据范围：**对于 100 % 100\% 100%的数据， 1 ≤ n ≤ 2 × 1 0 9 , 1 ≤ m ≤ 1 0 9 + 10 1\leq n \leq2 \times 10^9,1 \leq m \leq10^9+10 1≤n≤2×109,1≤m≤109+10
分析
已知 f n ? 1 = f n ? 1 + 0 × f n ? 2 f_{n-1}=f_{n-1}+0 \times f_{n-2} fn?1?=fn?1?+0×fn?2?
构造一维递推式和相同维数的方阵
一维递推式：
第一种：
f j ′ + = f k × a k j f_j{'}+=f_k\times a_{kj} fj?′+=fk?×akj?
即
?
[
f
1
f
2
f
3
?
]
×
[
a
11
a
12
a
13
a
21
a
22
a
23
a
31
a
32
a
33
]
?
=
?
[
f
1
′
f
2
′
f
3
′
?
]
\begin{matrix} \ [ f_1 & f_2&f_3 \ ] \times \end{matrix} \Bigg[ \begin{matrix} a_{11}& a_{1 2}&a_{13}\\ a_{21}&a_{22}&a_{23}\\ a_{31}&a_{32}&a_{33} \end{matrix} \Bigg ] \ = \ [ \begin{matrix} f_1{'}& f_2{'}&f_3{'} \end{matrix} \ ]
?[f1??f2??f3??]×?[a11?a21?a31??a12?a22?a32??a13?a23?a33??]?=?[f1?′?f2?′?f3?′??]
第二种：
f i ′ + = f k × a i k f_i{'}+=f_{k} \times a_{ik} fi?′+=fk?×aik?
即
[
f
1
f
2
]
×
[
a
11
a
12
a
21
a
22
]
?
=
[
f
1
′
f
2
′
]
\Big [ \begin{matrix} f_1\\ f_2\\ \end{matrix} \Big ] \times \Big [ \begin{matrix} a_{11}& a{12}\\ a_{21}& a_{22} \end{matrix} \Big ] \ = \Big [ \begin{matrix} f_1{'}\\ f_2{'} \end{matrix} \Big ]
[f1?f2??]×[a11?a21??a12a22??]?=[f1?′f2?′?]
推导
把
f
n
f_n
fn?和
f
n
?
1
f_{n-1}
fn?1?写成
2
?
1
2*1
2?1的矩阵
[
f
n
f
n
?
1
]
?
=
[
f
n
?
1
+
f
n
?
2
f
n
?
1
]
\Big [ \begin{matrix} f_n\\ f_{n-1} \end{matrix} \Big ] \ = \Big [ \begin{matrix} f_{n-1}+f_{n-2} \\ f_{n-1} \end{matrix} \Big ]
[fn?fn?1??]?=[fn?1?+fn?2?fn?1??]
? = [ 1 × f n ? 1 + 1 × f n ? 2 1 × f n ? 1 + 0 × f n ? 2 ] \ = \Big [ \begin{matrix} 1 \times f_{n-1}+1\times f_{n-2}\\ 1\times f_{n-1}+0\times f_{n-2} \end{matrix} \Big ] ?=[1×fn?1?+1×fn?2?1×fn?1?+0×fn?2??]
? = [ 1 1 1 0 ] × [ f n ? 1 f n ? 2 ] \ = \Big [ \begin{matrix} 1&1\\ 1&0 \end{matrix} \Big ] \times \Big[ \begin{matrix} f_{n-1}\\ f_{n-2} \end{matrix} \Big ] ?=[11?10?]×[fn?1?fn?2??]
? = [ 1 1 1 0 ] n ? 1 × [ f 1 f 0 ] \ = \Big[ \begin{matrix} 1&1\\ 1&0 \end{matrix} \Big ] ^{n-1} \times \Big [ \begin{matrix} f_1\\ f_0 \end{matrix} \Big ] ?=[11?10?]n?1×[f1?f0??]
? = [ 1 1 1 0 ] n ? 1 × [ 1 0 ] \ = \Big [ \begin{matrix} 1&1\\ 1&0 \end{matrix} \Big ] ^{n-1} \times \Big [ \begin{matrix} 1\\ 0 \end{matrix} \Big ] ?=[11?10?]n?1×[10?]
所以求 f n f_n fn?等求矩阵 [ 1 1 1 0 ] \Big [ \begin{matrix} 1&1\\ 1&0\end{matrix} \Big ] [11?10?]的 n ? 2 n-2 n?2次方
结果为第一行第一列的元素加上第二行第一列的数
或者：
求矩阵的n-1次方，结果为第一行的第一个数
Code
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<string>
#include<cmath>
#include<queue>
#include<stack>
#include<set>
#include<map>
#include<vector>
#define ll long long
#define maxn 100
#define lson (x<<1)
#define rson (x<<1|1)
using namespace std;
ll n,m,mod;
struct node{
ll a[maxn][maxn];
}p,g;
//矩阵g存最终答案
void init(node &x){//单位矩阵
for(ll i=1;i<=2;i++){
for(ll j=1;j<=2;j++){
if(i==j){
x.a[i][j]=1;
}
else x.a[i][j]=0;
}
}
// |1 0|
// |0 1|
}
void mul(node &x,node &y,node &t){//矩阵乘法
memset(t.a,0,sizeof(t.a));
for(ll i=1;i<=2;i++){
for(ll j=1;j<=2;j++){
for(ll k=1;k<=2;k++){
t.a[i][j]+=x.a[i][k]*y.a[k][j];
t.a[i][j]%=mod;
}
}
}
}
void ksm(ll k){//快速幂
//矩阵f存底数
//mul(i,j,t)矩阵i和矩阵j相乘的答案存储在矩阵t中
init(g);//根据：任何矩阵与单位矩阵相乘都等于本身
node t,f=p;
while(k){
if(k&1){
mul(g,f,t);
g=t;
//g=g*f 答案*底数的一次幂
}
mul(f,f,t);//底数加倍
f=t;
k>>=1;
}
}
int main(){
scanf("%lld%lld",&n,&mod);
p.a[1][1]=1;
p.a[1][2]=1;
p.a[2][1]=1;
p.a[2][2]=0;
if(n<=2){
printf("1\n");
}
else {
ksm(n-2);
ll ans=(g.a[1][1]%mod+g.a[1][2]%mod+mod)%mod;
printf("%lld\n",ans);
}
return 0;
}
