题目“AcWing 1303”的C++代码

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int N=3;
int n,m;

void mul(int a[][3],int b[][3],int c[][3]) {
    int t[3][3];
    memset(t,0,sizeof t);

    for(int i=0; i<3; i++)
        for(int j=0; j<3; j++)
            for(int k=0; k<3; k++)
                t[i][j]=(t[i][j]+(LL)a[i][k]*b[k][j]%m)%m;

    memcpy(c,t,sizeof t);
}

int main() {
    int a[N][N]= {
        {1,0,0},
        {0,0,0},
        {0,0,0}
    };

    int b[N][N]= {
        {1,1,1},
        {1,0,0},
        {0,0,1}
    };

    cin>>n>>m;
    while(n) { //fastPow
        if(n & 1) mul(a,b,a);
        mul(b,b,b);
        n>>=1;
    }
    cout<<a[0][2]<<endl;

    return 0;
}

/*
in:
5 1000

out:
12
*/