记录编号	584903	评测结果	AAAAAAAAAA
题目名称	五彩的色子	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.000 s
提交时间	2023-11-16 20:46:23	内存使用	0.00 MiB

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,p;
struct Matrix{
    ll a[4][4],n,m;
    void clear(){
        n = m = 0;
        memset(a,0,sizeof(a));
    }
    Matrix operator * (const Matrix &x)const{
        Matrix y;y.clear();
        y.n = n,y.m = m;
        for(int i = 0;i < n;i++)
            for(int j = 0;j < m;j++)
                for(int k = 0;k < m;k++)
                    y.a[i][j] = (y.a[i][j] + (a[i][k] * x.a[k][j]) % p) % p;
        return y;
    }
}c,f;
int main(){
    freopen("colorful.in","r",stdin);
    freopen("colorful.out","w",stdout);
    scanf("%lld%lld%lld",&n,&m,&p);
    if(n == 1){
        printf("%lld\n",(m-1)%p);
        return 0;
    }
    n -= 1;
    f.n = 1,f.m = 4;
    f.a[0][0] = 0,f.a[0][1] = 1,f.a[0][2] = m-1,f.a[0][3] = 0;
    c.n = c.m = 4;
    c.a[1][0] = 1,c.a[3][0] = 1,c.a[0][1] = 1,c.a[2][1] = 1;
    c.a[0][2] = m-1,c.a[2][2] = m-1,c.a[1][3] = m-1,c.a[3][3] = m-1;
    while(n){
        if(n & 1)f = f * c;
        c = c * c;
        n >>= 1;
    }
    printf("%lld\n",(f.a[0][0]+f.a[0][2])%p);
    
    return 0;
    
}