快速幂与矩阵乘法的结合（斐波那契数列）

#include
using namespace std;
typedef long long ll;
int n,p;
ll m;
struct node{
    //save
    ll g[4][4];
}f,res;
void ORI(node &x){ //单位矩阵
    for(int i = 1;i <= 2;i++){
        for(int j = 1;j <= 2;j++){
            if(i==j) x.g[i][j] = 1LL;
            else x.g[i][j] = 0LL;
        }
    }
}
void sq_t(node &x,node &y,node &z){
    memset(z.g,0,sizeof(z.g));//预设结果矩阵为空
    int i,j,k;
    for(i = 1;i <= 2;i++){
        for(k = 1;k <= 2;k++){
            for(j = 1;j <= 2;j++){
                z.g[i][k] += x.g[i][j] * y.g[j][k]; //计算
                if(z.g[i][k] >= m) {z.g[i][k] %= m;} //驱魔
                
            }
        }
    }
}
void outp(node &x){
    for(int i = 1;i <= 2;i++){
        for(int k = 1;k <= 2;k++){
            cout<        }
        printf("\n");
    }
    printf("END\n\n");
}
void ksm(int yy){
    ORI(res);//预设结果为单位矩阵(y = 1)
    node temp,t;
    temp = f;//预设操作矩阵为f矩阵
    while(yy){
        if(yy&1) {
            sq_t(res,temp,t);res = t;//y = y*x
        }
        sq_t(temp,temp,t);temp = t;//x = x*x
        yy>>=1;
    }
}
ll solve(){         //即原递推函数，需要考虑特判_公式_取模
    if(n <= 2) return 1LL;
    ksm(n - 2);  //此时的res为基本数组的幂 ，需乘（1，1），即同行下相加为对应列 数字
    ll ans = res.g[1][1] + res.g[2][1];//结合上面就好理解了，ans为乘完（1，1）后第一个数
    if(ans >= m) ans %= m;//驱魔
    return ans;
}
int main(){
    
    scanf("%d%d",&n,&p);
    m=p;
    f.g[1][1] = 1;f.g[1][2] = 1;f.g[2][1] = 1;f.g[2][2] = 0;
    //f是递推推出来的基本数组，即x^y中x
    int endr = (int)solve();
    printf("%d",endr);
    return 0;
}