矩阵——普通递推数列

概述

最近学习了一下矩阵，终于在疯狂敲了3遍+手写2遍之后能够一节课之内打完了，高兴啊！！！
大概简述一下思路，首先是一个快读，以前看别人打快读那么长以为有多么难，现在仔细一看发现原来没那么难…
之后封装了一个matrix结构体，之后matrix就可以和其他数据结构一样用啦！！！
之后重定义了一下矩阵的乘法运算，还有矩阵的幂次运算，最后读入n:询问的项数，k:递推数列的系数个数，A：递推数列的系数，f0:递推数列的初始值
然后计算就好了…

code

#include<cstdio> 
#include<cstring>
#include<algorithm>
using namespace std;
int read()
{
    int f=1,s=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9')
    {
        s=(s<<1)+(s<<3)+ch-'0';
        ch=getchar();
    }
    return f*s;
}
const int maxn=101,maxm=101,mod=10000;
struct matrix
{
    int n,m;
    long long s[maxn][maxm];
    matrix(){clean();}
    void clean()
    {
        n=maxn,m=maxm;
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                s[i][j]=0;
    }
}A,f0;
matrix operator * (matrix a,matrix b)
{
    matrix c;
    if(a.m!=b.n)return c;
    c.n=a.n,c.m=b.m;
    long long ss[maxn];
    for(int j=0;j<c.m;j++)
    {
        for(int i=0;i<b.n;i++)ss[i]=b.s[i][j];
        for(int i=0;i<c.n;i++)
        {
            for(int k=0;k<b.n;k++)
                c.s[i][j]+=a.s[i][k]*ss[k];
            c.s[i][j]%=mod;
        }
    }
    return c;
}
matrix pow(matrix a,int b)
{
    matrix ans;
    ans.n=ans.m=a.n;
    for(int i=0;i<a.n;i++)
        for(int j=0;j<a.m;j++)
            ans.s[i][j]=(i==j);
    for(;b;b>>=1,a=a*a)if(b&1)ans=ans*a;
    return ans;        
}
int n,k;
int main()
{
    n=read();
    k=read();
    for(int i=0;i<k;i++)A.s[0][i]=read();
    for(int i=0;i<k;i++)f0.s[k-i-1][0]=read();
    for(int i=1;i<k;i++)A.s[i][i-1]=1;
    A.n=A.m=k;
    f0.n=k,f0.m=1;
    if(n<k)
    {
        printf("%lld",f0.s[k-n-1][0]);
        return 0;
    }
    matrix tmp=pow(A,1);
    printf("%lld",(pow(A,n-k+1)*f0).s[0][0]);
    return 0;
}