BZOJ3231(矩阵连乘，稍有点复杂)

题意：

一个由自然数组成的数列按下式定义：

对于i <= k：ai = bi
对于i > k: ai = c1ai-1 + c2ai-2 + ... + ckai-k
其中bj和 cj （1<=j<=k）是给定的自然数。写一个程序，给定自然数m <= n, 计算am + am+1 + am+2 + ... + an, 并输出它除以给定自然数p的余数的值。1<= k<=15，1 <= m <= n <= 10^18

本题主要是构造矩阵，然后就直接矩阵连乘即可。

构造的上述矩阵的i大于k，当i小于k时就直接加起来就行。

这样am + am+1 + am+2 + ... + an=S(n)-S(m-1)

代码：

#include 
#include 
#include 

using namespace std;
typedef long long LL;
const int MAXN=25;

struct Matrix
{
    LL m[MAXN][MAXN];
};

LL b[MAXN],c[MAXN];
LL K,M,N,P;
Matrix a,per;

void Init()
{
    int i,j;
    for(i=0;i<=K;i++)
        for(j=0;j<=K;j++)
            per.m[i][j]=(i==j);
}

Matrix multi(Matrix a,Matrix b)
{
    Matrix c;
    int i,j,k;
    for(i=0;i<=K;i++)
    {
        for(j=0;j<=K;j++)
        {
            c.m[i][j]=0;
            for(k=0;k<=K;k++)
                c.m[i][j]+=a.m[i][k]*b.m[k][j]%P;
            c.m[i][j]%=P;
        }
    }
    return c;
}

Matrix matrix_mod(LL n)
{
    Matrix ans=per,p=a;
    while(n)
    {
        if(n&1)
        {
            ans=multi(ans,p);
            n--;
        }
        n>>=1;
        p=multi(p,p);
    }
    return ans;
}

int main()
{
    int i,j;
    Init();
    LL ret1,ret2,S;
    Matrix ans;
    while(cin>>K)
    {
        ret1=ret2=0;
        for(i=0;i>b[i];
        for(i=0;i>c[i];
        cin>>M>>N>>P;
        for(i=0;i0)  a.m[i][j]=c[j-1];
                if(i==1&&j>0)  a.m[i][j]=c[j-1];
                if(i>1)        a.m[i][j]=(i==(j+1));
            }
        }
        S=0;
        for(i=0;i=2)
            for(i=0;i<=M-2;i++)
            {
                ret2+=b[i];
                ret2%=P;
            }
            if(M<2) ret2=0;
        }
        else
        {
            ans=matrix_mod(M-K-1);
            ret2=ans.m[0][0]*S%P;
            for(i=1;i<=K;i++)
            {
                ret2+=ans.m[0][i]*b[K-i]%P;
                ret2%=P;
            }
        }
        cout<<((ret1-ret2)%P+P)%P<