题解 P2461 【[SDOI2008]递归数列】

# 矩阵乘法 线性递推式，求几项之和 按照惯例，我们先手推一波~~虽然并推不出来~~ 设当前项为 $a_i$ 当$i\leqslant k$ 时 $$a_i=b_i$$ 当$i>k$ 时 $$a_i= \sum_{j=1}^{k} c_j*a_{i-j}$$ 同理 $$a_{i+1}= \sum_{j=1}^{k} c_j * a_{i-j+1}$$ 我们尝试着减一下 $$a_{i+1}-a_i= \sum_{j=1}^{k} c_j * ( a_{i-j+1}-a_{i-j} )$$ 然后我们逐渐往前推，便可以得到一个性质 $a_i-a_{i-1}=$ 之前所有的差乘上一个$c_j$ ~~这不是废话吗，题意显然啊~~ 接下来我们便可以构造出这么一个矩阵 ~~那你直接给矩阵不好吗~~ $sum[i]$ 表示的是$b_i$的前缀和,我们先假设$\quad k=3$ $( a_{n-2} \quad a_{n-1} \quad a_n \quad s_n )$=$(a_1\quad a_2\quad a_3 \quad s_3)$ $\begin{bmatrix}0&0&c_3&c_3\\1&0&c_2&c_2\\0&1&c_1&c_1\\0&0&0&1\\\end{bmatrix}^{n-3}$ 举完例子，我们再详细说一下矩阵($k*k$)具体构造 对于第$i$行（$1<=i<=k$），我们从第$k$个开始（前面全部用0填充），之后全部用 $c_{k-i+1}$ 进行填充 然后我们对于第$i$行（$1<=i<=k$）再进行一次对角线填充 最后我们再多加上一行，在最后一个填充一个1，完成对角线填充 然后我们就可以愉快的开始快速幂处理了 ``` #include<bits/stdc++.h> #define ll long long using namespace std; inline ll read() { ll x=0; char c=getchar(); bool flag=0; while(c<'0'||c>'9') {if(c=='-')flag=1;c=getchar();} while(c>='0'&&c<='9'){x=(x+(x<<2)<<1)+ c-'0';c=getchar();} return flag?-x:x; } const int N=20; ll K,b[N],c[N],sum[N],ans1,ans2,mod,n,m; struct Matrix { int l,r; ll a[N][N]; Matrix(){}; Matrix(int x,int y):l(x),r(y){ memset(a,0,sizeof(a));} Matrix operator*(Matrix t) { Matrix cg=Matrix(l,t.r); for(int i=1;i<=l;++i) for(int j=1;j<=t.r;++j) for(int k=1;k<=r;++k) cg.a[i][j]=(cg.a[i][j]+a[i][k]*t.a[k][j]%mod)%mod; return cg; } Matrix operator^(ll p) { Matrix t=Matrix(l,r),cg=Matrix(l,r); memcpy(t.a,a,sizeof(a)); if(p&1) memcpy(cg.a,a,sizeof(a)); else for(int i=1;i<=l;++i) cg.a[i][i]=1; while(p>>=1) { t=t*t; if(p&1) cg=cg*t; } return cg; } }st,ed; int main() { K=read(); st=Matrix(1,K+1); for(int i=1;i<=K;++i) b[i]=read(); for(int i=1;i<=K;++i) c[i]=read(); m=read(),n=read(),mod=read(); for(int i=1;i<=K;++i) sum[i]=(sum[i-1]+b[i])%mod,st.a[1][i]=b[i]%mod,c[i]%=mod; if(n<=K) {printf("%lld\n",(sum[n]-sum[m-1]+mod)%mod);return 0;} ed=Matrix(K+1,K+1); for(int i=1;i<=K;++i) ed.a[i][K]=ed.a[i][K+1]=c[K-i+1]; for(int i=2;i<=K;++i) ed.a[i][i-1]=1; ed.a[K+1][K+1]=1,st.a[1][K+1]=sum[K]; if(m>K) ans1=(st*(ed^(m-K-1))).a[1][K+1]; else ans1=sum[m-1]; ans2=(st*(ed^(n-K))).a[1][K+1]; printf("%lld\n",(ans2-ans1+mod)%mod); } ```