矩阵快速幂--构造

参考：https://blog.****.net/protecteyesight/article/details/72820799

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL a, b,n, m;
struct mat
{
    LL a[3][3];
    mat()
    {
        memset(a, 0, sizeof(a));
    }
    mat operator *(const mat q)
    {
        mat c;
        for(int i = 1; i <= 2; ++i)
            for(int j = 1; j <= 2; ++j)
                if(a[i][j])
                    for(int k = 1; k <= 2; ++k)
                    {
                        c.a[i][k] += a[i][j] * q.a[j][k];
                        if (c.a[i][k] >= m)
                            c.a[i][k] %= m;
                    }
        return c;
    }
};

mat qpow(mat x, LL n)
{
    mat ans;
    ans.a[1][1] = ans.a[2][2] = 1;
    while(n)
    {
        if (n&1)
            ans = ans * x;
        x = x * x;
        n >>= 1;
    }
    return ans;
}


int main()
{
    while(scanf("%lld %lld %lld %lld", &a, &b, &n, &m) != EOF)
    {
        mat ans;
        a = a % m;
        b = b %m;
        ans.a[1][1] = ans.a[2][2] =a;
        ans.a[1][2] =  b;
        ans.a[2][1] = 1;
        ans = qpow(ans, n);
        LL sum = ans.a[1][1];
        sum = (sum * 2) % m;
        printf("%lld\n",sum);
    }
    return 0;
}