题目链接
众所周知，蓝色是水的颜色，所以这是道水题（doge）
前置知识
矩阵、快速幂、最大公因数。
矩阵
假设原矩阵为 a 和 b 。
则矩阵有以下运算。
矩阵加法
一个一个加，即：
c_{i,j}=a_{i,j}+b_{i,j}
矩阵乘法
一行一列乘，即：
c_{i,j}=\sum^n_{k=1}a_{i,k}\times b_{k,j}
结合律
(ab)c=a(bc)
单位矩阵
主对角线上都为 1 的矩阵。
了解这些就够了。
快速幂
例：
求 2^{19} 。
- 先将指数化为二进制。
19=10011_2 - 再将底数不断平方 。
2^1=2
2^2=4
4^2=16
16^2=256
256^2=65536 - 将对应的位置上乘上对应的权值。
2^{19}=65536\times4\times2=请自行计算
程序实现：
int ksm(int n,int m){
int res=1;
while(m){
if(n%2==1) res=n*res;
n=n*n;
m/=2;
}
return res;
}
最大公约数
数论只会GCD。
太简单了，不讲。
思路梳理
让我们求 (f_n,f_m) 。
就相当于让我们求 f_{(n,m)} 。
别问我怎么知道的，问就是打表打出来的。
首先用求出 n 和 m 的最大公因数。
然后再用矩阵快速幂求出 f_{(n,m)} 。
实现方法：
计算矩阵
1\,\,\,\,1\\
1\,\,\,\,0
的 (n,m)-1 次方。
代码实现
矩阵乘法核心代码：
jz operator *(jz a,jz b){
jz res={};
for(int i=1;i<=2;i++){
for(int j=1;j<=2;j++){
int sum=0;
for(int k=1;k<=2;k++){
sum+=a.a[i][k]%mod*b.a[k][j]%mod;
sum%=mod;
}
res.a[i][j]=sum%mod;
res.a[i][j]%=mod;
}
}
return res;
}
矩阵快速幂核心代码：
jz ksm(jz a,int n){
jz res={};
res.a[1][1]=1;
res.a[2][2]=1;
while(n){
if(n%2==1) res=a*res;
a=a*a;
n/=2;
}
return res;
}
最大公因数核心代码：
int Gcd(int x,int y){
if(y==0) return x;
return Gcd(y,x%y);
}
最后，完整代码。
想要吗，不给
发AC代码是要被封号的！！！