题面：BZOJ传送门 洛谷传送门 这个递推式挺恶心的。。。 首先， 而且要求区间和（这个其实简单）我们差分一下就好了 那么我们构造矩阵递推式（要把前缀和也搞进去） 和noi2012的那题随机数生成器一样，我们还是可以通过结合律把前面的先算出来再把后面的乘上去，就变成了这样： 然后就可以矩阵快速幂解决了 如果询问的n小于k的话直接暴力求前面的就好了 ps：这题变量要全开long long，我调了一个上午。。。
#include<bits/stdc++.h> using namespace std; typedef long long ll; struct juzhen{ll a[20][20];}x,s,c; ll B[20],C[20]; ll K,MOD,ss=0; inline juzhen cheng(juzhen a,juzhen b){ memset(c.a,0,sizeof c.a); for(ll i=1;i<=K+1;i++) for(ll j=1;j<=K+1;j++) for(ll k=1;k<=K+1;k++)(c.a[i][j]+=a.a[i][k]*b.a[k][j])%=MOD; return c; } inline juzhen mi(juzhen y,ll b){ x=y; while(b!=0){ if(b&1==1)x=cheng(x,y); y=cheng(y,y);b>>=1; } return x; } inline ll gaoshi(ll x){ if(x<=K){ ll sum=0; for(ll i=1;i<=x;i++)(sum+=B[i])%=MOD; return sum; } memset(s.a,0,sizeof s.a); s.a[1][1]=1;for(ll i=3;i<=K+1;i++)s.a[i][i-1]=1; for(ll i=2;i<=K+1;i++)s.a[1][i]=s.a[2][i]=C[i-1]; s=mi(s,x-K-1); ll ans=ss; for(ll i=2;i<=K+1;i++)(ans+=s.a[1][i]*B[K-i+2]%MOD)%=MOD; return ans; } int main() { scanf("%lld",&K); for(ll i=1;i<=K;i++)scanf("%lld",&B[i]); for(ll i=1;i<=K;i++)scanf("%lld",&C[i]); ll n,m;scanf("%lld%lld%lld",&m,&n,&MOD); for(ll i=1;i<=K;i++)(ss+=B[i])%=MOD; ll ans=(gaoshi(n)%MOD-gaoshi(m-1)%MOD+MOD)%MOD; printf("%lld",ans); return 0; }