学步园

其实就是一个矩阵加上等比数列求和的问题，在因为b等于0的问题上卡住了，最后看了人家的解法重新构造了乘数矩阵

code：

#include <ctime>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <map>
#define LL long long
using namespace std;


LL k,b,n,M;

struct Matrix
{
    LL mat[3][3];
}A,E;

Matrix operator + (const Matrix a,const Matrix b)
{
    Matrix res;
    int i,j;
    for(i=1;i<=2;i++)
    {
        for(j=1;j<=2;j++)
        {
            res.mat[i][j] = (a.mat[i][j] + b.mat[i][j])%M;
        }
    }
    return res;
}

Matrix operator * (const Matrix a,const Matrix b)
{
    Matrix res;
    int i,j,k;
    for(i=1;i<=2;i++)
    {
        for(j=1;j<=2;j++)
        {
            res.mat[i][j] = 0;
            for(k=1;k<=2;k++)
            {
                res.mat[i][j] = (res.mat[i][j] + a.mat[i][k]*b.mat[k][j]%M )%M;
            }
        }
    }
    return res;
}

Matrix operator ^ (const Matrix a,LL exp)
{
    Matrix tmp=a;
    Matrix res=E;
    while(exp)
    {
        if(exp & 1)
            res = res *tmp;
        exp >>= 1;
        tmp = tmp * tmp;
    }
    return res;
}

Matrix GetSum(Matrix a,LL k)
{
    if(k==1)
        return a;
    if(k&1)
        return GetSum(a,k-1) + (a^k);
    return GetSum(a,k>>1) * ( (a^(k>>1)) + E) ;
}

void init()
{
    memset(A.mat,0,sizeof(A.mat));
    memset(E.mat,0,sizeof(E.mat));
    A.mat[1][2]=A.mat[2][2]=A.mat[2][1]=1;
    E.mat[1][1]=E.mat[2][2]=1;
}

int main()
{
    init();
    Matrix t,ans;
    while(~scanf("%lld%lld%lld%lld",&k,&b,&n,&M))
    {
        t = A ^ k;
        ans = GetSum(t,n-1) + E ;
        ans = (A ^ b) * ans ;
        printf("%lld\n",ans.mat[2][1]);
    }
    return 0;
}