学步园

以后遇到这种数据接近 limit 的必须小心  乘法!

要不就全用long long   __int64

推倒~

g(i)=k*i+b;代入Si  得

sn=f(b)+f(k+b)+f(2*k+b)+...+f((n-1)k+b)

建立斐波那契的递推的矩阵 A

sn=A^b * (I+A^K+...+A^((n-1)*K))  * (f[0]#f[1])

(I为单位矩阵)

设 R 为A^K

构造矩阵

代入  ..AC

#include <stdio.h>
#include <string.h>
#define ff(i,n) for(int i=0;i<n;i++)

int M;

struct Mat
{
    int m[2][2];
    friend Mat operator*(Mat a,Mat b)
    {
        Mat c;
        memset(c.m,0,sizeof(c.m));
        ff(i,2)
        ff(j,2)
        ff(k,2)
        {
            c.m[i][j]+=((<span style="color:#FF0000;">long long</span>)(a.m[i][k]%M)*(b.m[k][j]%M))%M;///care
            c.m[i][j]%=M;
        }
        return c;
    }
    friend Mat operator+(Mat a,Mat b)
    {
        ff(i,2)
        ff(j,2)
        {
            a.m[i][j]+=b.m[i][j]%M;
            a.m[i][j]%=M;
        }
        return a;
    }
}I,R,A;

void DEBUG(Mat a)
{
    ff(i,2)
    {
        ff(j,2)
            printf("%d\t",a.m[i][j]);
        puts("");
    }
    puts("");
}

struct SMat
{
    Mat m[2][2];
    friend SMat operator*(SMat a,SMat b)
    {
        SMat c;
        memset(c.m,0,sizeof(c.m));
        ff(i,2)
        ff(j,2)
        ff(k,2)
            c.m[i][j]=c.m[i][j]+a.m[i][k]*b.m[k][j];
        return c;
    }
}W;

Mat Power(Mat a,int n)
{
    Mat c;
    memset(c.m,0,sizeof(c.m));
    ff(i,2)
        c.m[i][i]=1;
    for(;n;n>>=1)
    {
        if(n&1)
            c=c*a;
        a=a*a;
    }
    return c;
}

SMat SPower(SMat a,int n)
{
    SMat c;
    memset(c.m,0,sizeof(c.m));
    ff(i,2)
        c.m[i][i]=I;
    for(;n;n>>=1)
    {
        if(n&1)
            c=c*a;
        a=a*a;
    }
    return c;
}


int main()
{
    //freopen("hdu1588in","r",stdin);
    memset(I.m,0,sizeof(I.m));
    memset(A.m,0,sizeof(A.m));
    memset(W.m,0,sizeof(W.m));
    I.m[0][0]=I.m[1][1]=A.m[0][1]=A.m[1][0]=A.m[1][1]=1;


    int k,b,n;
    while(scanf("%d%d%d%d",&k,&b,&n,&M)!=EOF)
    {
        W.m[0][1]=W.m[1][1]=I;
        R=Power(A,k);
        Mat a=Power(A,b);
        SMat w=W;
        w.m[0][0]=R;
        w=SPower(w,n);
        a=a*w.m[0][1];
        //DEBUG(I);
        printf("%d\n",a.m[0][1]%M);
    }
    return 0;
}