sdut- D - K-based Numbers. Version 3

这个依旧是矩阵快速幂，只是需要用到快速乘

链接：https://cn.vjudge.net/contest/283989#problem/D

#include<bits/stdc++.h>
using namespace std;
struct node
{
   
    long long a[2][2];
};
node c, ans;
long long n, k, M;
long long nmul(long long x, long long y, long long MOD)//快速乘
{
   
    long long sum = 0;
    x = x%MOD;
    y = y%MOD;
    while(y)
    {
   
        if(y&1)//满足条件，加一波
        {
   
            sum = (sum + x)%MOD;
        }
        y >>= 1;
        x = (x+x)%MOD;//自加一波
    }
    return sum;
}
node mul(node x, node y, long long MOD)//矩阵相乘
{
   
    node sum;
    memset(sum.a, 0, sizeof(sum.a));
    for(int k = 0; k < 2; k++)
    {
   
        for(int i = 0; i < 2; i++)
        {
   
            if(x.a[i][k])
                for(int j = 0; j < 2; j++)
                {
   
                    sum.a[i][j] += nmul(x.a[i][k], y.a[k][j], MOD);
                    sum.a[i][j] %= MOD;
                }
        }
    }
    return sum;
}
node fp(node t, long long n, long long MOD)//矩阵快速幂
{
   
    node sum;
    memset(sum.a, 0, sizeof(sum.a));
    for(int i = 0; i < 2; i++)
        sum.a[i][i] = 1;//单位矩阵
    while(n)
    {
   
        if(n&1)//满足条件，sum乘一波t
        {
   
            sum = mul(sum, t, MOD);
        }
        n >>= 1;//去掉n的二进制最后一位
        t = mul(t, t, MOD);//自乘一波
    }
    return sum;
}
void init()//初始化
{
   
    c.a[0][0] = c.a[0][1] = k-1;
    c.a[1][0] = 1, c.a[1][1] = 0;
    memset(ans.a, 0, sizeof(ans.a));
    ans.a[0][0] = k-1;
    /************************ c: k-1 k-1 1 0 ans: k-1 0 0 0 ************************/
}
int main()
{
   
    while(cin >> n >> k >> M)
    {
   
        init();
        node t = fp(c, n-1, M);
        t = mul(t, ans, M);
        cout << (t.a[0][0] + t.a[1][0]) % M << endl;
    }
    return 0;
}
//这种题，关键在于矩阵快速幂和矩阵相乘
//矩阵快速幂和快速幂的套路是一样的，只是乘的东西不一样，矩阵相乘也是一个固定的套路
//快速乘据解释是和快速幂一样的东西，快速幂相乘的地方变成相加就是快速乘
//还有就是看了好多博客，都是结构体里面整一个二维数组，有点不习惯结构体里面开数组
//以及里面开了一个很骚的操作
/** struct node { long long a[maxn][maxn]; node { memset(a, 0, sizeof(a); } }; **/
//代表每次建一个新的变量名（如p）时，p.a[i(0->maxn)]=0;