矩阵快速幂模板

#include <cstdio>#include <iostream>#include <algorithm>#include <cmath>#include <cstring>using namespace std;typedef long long ll;const int N = 20;int msize, Mod;struct Mat{    ll mat[N][N];};Mat operator *(Mat a, Mat b){    Mat c;    memset(c.mat, 0, sizeof(c.mat));    for(int k = 0; k < msize; ++k)        for(int i = 0; i < msize; ++i)            if(a.mat[i][k])                for(int j = 0; j < msize; ++j)                    if(b.mat[k][j])                        c.mat[i][j] = (c.mat[i][j] +a.mat[i][k] * b.mat[k][j])%Mod;    return c;}Mat operator ^(Mat a, int k){    Mat c;    memset(c.mat,0,sizeof(c.mat));    for(int i = 0; i < msize; ++i)        c.mat[i][i]=1;    for(; k; k >>= 1)    {        if(k&1) c = c*a;        a = a*a;    }    return c;}int main(){//    freopen("in.txt","r",stdin);    int n;    int a[20] ,f[20];    while(~scanf("%d%d%d", &msize, &n, &Mod))    {        if(msize == 0) break;        for(int i = 0; i < msize; i++)            scanf("%d", &a[i]);        for(int i = msize-1; i >= 0; i--)            scanf("%d", &f[i]);        Mat A;        memset(A.mat,0,sizeof(A.mat));        for(int i = 0; i < msize; i++)            A.mat[0][i] = a[i];        for(int i = 1; i < msize; i++)            A.mat[i][i-1] = 1;        A = A^(n - msize);        ll ans = 0;        for(int i=0; i < msize; i++)            ans = (ans + A.mat[0][i]*f[i]) % Mod;        printf("%lld\n", ans);    }    return 0;}