矩阵——普通递推数列

概述

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

code

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