BZOJ_3231_[Sdoi2008]递归数列

BZOJ_3231_[Sdoi2008]递归数列_矩阵乘法

Description

一个由自然数组成的数列按下式定义：

对于i <= k：a_i = b_i

对于i > k: a_i = c₁a_i-1 + c₂a_i-2 + ... + c_ka_i-k

其中b_j和 c_j （1<=j<=k）是给定的自然数。写一个程序，给定自然数m <= n, 计算a_m + a_m+1 + a_m+2 + ... + a_n, 并输出它除以给定自然数p的余数的值。

Input

由四行组成。

第一行是一个自然数k。

第二行包含k个自然数b₁, b₂,...,b_k。

第三行包含k个自然数c₁, c₂,...,c_k。

第四行包含三个自然数m, n, p。

Output

仅包含一行：一个正整数，表示(a_m + a_m+1 + a_m+2 + ... + a_n) mod p的值。

Sample Input

2
1 1
1 1
2 10 1000003

Sample Output

142

HINT

对于100%的测试数据：

1<= k<=15

1 <= m <= n <= 1018

用c矩阵做矩阵乘法。

由于需要求和我们在矩阵中加一项表示Sn。

然后直接上矩阵快速幂。

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

typedef long long ll;

#define N 20

ll p,c[N],a[N],b[N],s[N];

int n,m;

struct Mat {

	ll v[N][N];

	Mat() {memset(v,0,sizeof(v));}

	Mat operator * (const Mat &x) const {

		Mat re; int i,j,k;

		for(i=1;i<=m;i++) {

			for(j=1;j<=m;j++) {

				for(k=1;k<=m;k++) {

					re.v[i][j]=(re.v[i][j]+v[i][k]*x.v[k][j])%p;

				}

			}

		}

		return re;

	}

}X;

Mat qp(Mat x,ll y) {

	Mat I;

	int i;

	for(i=1;i<=m;i++) I.v[i][i]=1;

	for(;y;y>>=1ll,x=x*x) if(y&1ll) I=I*x;

	return I;

}

ll getS(ll y) {

	if(y<=n) return s[y];

	Mat T=qp(X,y-n);

	ll re=0;

	int i;

	for(i=1;i<=n;i++) re=(re+a[i]*T.v[m][i])%p;

	re=(re+s[n]*T.v[m][m])%p;

	return re;

}

int main() {

	scanf("%d",&n);

	int i;

	ll l,r;

	for(i=1;i<=n;i++) scanf("%lld",&b[i]);

	for(i=1;i<=n;i++) scanf("%lld",&c[i]);

	scanf("%lld%lld%lld",&l,&r,&p);

	for(i=1;i<=n;i++) a[n-i+1]=b[i];

	for(i=1;i<=n;i++) s[i]=s[i-1]+a[i];

	for(i=1;i<=n;i++) X.v[1][i]=X.v[n+1][i]=c[i];

	for(i=2;i<=n;i++) X.v[i][i-1]=1;

	m=n+1;

	X.v[m][m]=1;

	// printf("%lld %lld\n",l,r);

	// printf("%lld\n",getS(l-1));

	printf("%lld\n",(getS(r)-getS(l-1)+p)%p);

}

巴特西