https://daniu.luogu.org/problem/show?pid=2461 这个矩阵贼明显的啊，然后查分一下； 当然这个矩阵还是后很多地方要注意的； 这道题其实可以在理解斐波那契矩阵后直接做；
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #define Ll long long using namespace std; struct jv{ int n,m; Ll a[16][16]; jv(){memset(a,0,sizeof a);} }met,zz; int b[16],c[16]; Ll n,m,mo,k,x,y; void out(jv a){ for(int i=1;i<=a.n;i++){ for(int j=1;j<=a.m;j++)cout<<a.a[i][j]<<' ';cout<<endl; }cout<<endl; } void make(){ met.n=met.m=k+1; for(int i=1;i<=k;i++)met.a[1][i]=c[i]%mo; for(int i=2;i<=k;i++)met.a[i][i-1]=1; met.a[k+1][1]=met.a[k+1][k+1]=1; // out(met); zz.n=k+1;zz.m=1; for(int i=1;i<=k;i++)zz.a[k-i+1][1]=b[i]%mo; for(int i=1;i<k;i++)zz.a[k+1][1]=(zz.a[k+1][1]+b[i])%mo; // out(zz); } jv cheng(jv a,jv b){ jv c; c.n=a.n; c.m=b.m; for(int i=1;i<=c.n;i++) for(int k=1;k<=a.m;k++)if(a.a[i][k]) for(int j=1;j<=c.m;j++) c.a[i][j]=(c.a[i][j]+a.a[i][k]*b.a[k][j])%mo; return c; } jv ksm(Ll n){ jv ans=met,c=met; for(n--;n;n>>=1,c=cheng(c,c)) if(n&1)ans=cheng(ans,c); return ans; } Ll find(Ll n){ if(n<=k)return b[n]; jv ans=cheng(ksm(n-k),zz); return (ans.a[k+1][1]+ans.a[1][1])%mo; } int main() { scanf("%lld",&k); for(int i=1;i<=k;i++)scanf("%d",&b[i]); for(int i=1;i<=k;i++)scanf("%d",&c[i]); scanf("%lld%lld%lld",&n,&m,&mo); make(); x=find(m); y=find(n-1); printf("%lld",((x-y)%mo+mo)%mo); }