题目

题目描述

大家都知道Fibonacci数列把，\(f_1=1,f_2=1,f_3=2,f_4=3,f_n=f_{n-1}+f_{n-2}\)
现在问题很简单，输入\(n\)和\(m\)，求\(f_n mod m\)

输入格式

输入\(n,m\)

输出格式

输出\(f_n mod m\)

样例输入

5 1000

5 1000

样例输出

5

数据范围与提示

对于\(100\%\)的数据，\(1\le n \le 2\times 10^9,1\le m\le 10^9 + 10\)

题解

看到这个数据范围，就知道这肯定不能够一般地递推了。
于是我们要介绍一个工具来帮助我们计算这个数列——矩阵乘法
两个矩阵的乘法仅当第一个矩阵A的列数和第二个矩阵B的行数相等的时候才能定义
就举个例子好了

\(\begin{bmatrix}1&0&2\\ -1&3&1\end{bmatrix} \times \begin{bmatrix} 3&1 \\ 2&1\\ 1&0\end{bmatrix}=\begin{bmatrix}(1\times3+0\times2+2\times0)&(1\times1+0\times1+2\times0) \\ (-1\times3+3\times2+1\times1)&(-1\times1+3\times1+1\times0)\end{bmatrix}\)

那么我们根据这个性质，可以定义两个矩阵，一个是数值矩阵用来存贮递推时的数据，需要有一个初始值，还有一个是递推矩阵用来定义如何递推。
在这道里，我们可以初始化数值矩阵为：

\(\begin{bmatrix}f_2&0\\f_1&0\end{bmatrix}\)

而我们定义递推矩阵为：

\(\begin{bmatrix}1&1\\1&0\end{bmatrix}\)

每次用数值矩阵乘递推矩阵，得到的新矩阵中，数列的下标正好是原来的下标+1，递推得以进行。（请读者自己动手体会一下，不然你永远只为停留在“哇，这个算法好神奇”这个层面）
而对于乘法的递推，我们很容易就想到快速幂，于是这道题就完美解决。
至于如何定义数值矩阵和递推矩阵，我认为还是要多自己思考，多做几次就会了。

代码

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
int n,mod;
long long res[3][3],mul[3][3];

void mul_res(){
    long long tmp[3][3];
    memset(tmp,0,sizeof(tmp));
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            for(int k=1;k<=2;k++){
                tmp[i][j]=(tmp[i][j]+mul[i][k]*res[k][j])%mod;
            }
        }
    }
    memcpy(res,tmp,sizeof(tmp));
}

void mul_mul(){
    long long tmp[3][3];
    memset(tmp,0,sizeof(tmp));
    for(int i=1;i<=2;i++){
        for(int j=1;j<=2;j++){
            for(int k=1;k<=2;k++){
                tmp[i][j]=(tmp[i][j]+mul[i][k]*mul[k][j])%mod;
            }
        }
    }
    memcpy(mul,tmp,sizeof(tmp));
}

int main(){
    cin>>n>>mod;
    if(n<=2){cout<<1;return 0;}
    res[1][1]=res[2][1]=1;
    mul[1][1]=mul[2][1]=mul[1][2]=1;
    n-=2;//初始状态我们可以认为已经是f2的时候了
    while(n){
        if(n&1)mul_res();
        mul_mul();
        n>>=1;
    }
    cout<<res[1][1];
    return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

int n,mod;

long long res[3][3],mul[3][3];

void mul_res(){

long long tmp[3][3];

memset(tmp,0,sizeof(tmp));

for(int i=1;i<=2;i++){

for(int j=1;j<=2;j++){

for(int k=1;k<=2;k++){

tmp[i][j]=(tmp[i][j]+mul[i][k]*res[k][j])%mod;

}

memcpy(res,tmp,sizeof(tmp));

}

void mul_mul(){

long long tmp[3][3];

memset(tmp,0,sizeof(tmp));

for(int i=1;i<=2;i++){

for(int j=1;j<=2;j++){

for(int k=1;k<=2;k++){

tmp[i][j]=(tmp[i][j]+mul[i][k]*mul[k][j])%mod;

}

memcpy(mul,tmp,sizeof(tmp));

}

int main(){

cin>>n>>mod;

if(n<=2){cout<<1;return 0;}

res[1][1]=res[2][1]=1;

mul[1][1]=mul[2][1]=mul[1][2]=1;

n-=2;//初始状态我们可以认为已经是f2的时候了

while(n){

if(n&1)mul_res();

mul_mul();

n>>=1;

}

cout<<res[1][1];

return 0;

}

题目