BZOJ-3231 [SDOI2008]递归数列

转成矩阵连乘后，矩阵快速幂加速解决。

一开始没把需要longlong的变量补全。。而且没初始化2333

#include <cstdlib>

#include <cstdio>

#include <cstring>

#include <cctype>

#include <cmath>

#include <algorithm>

#include <iostream>

#define rep(i, l, r) for(int i=l; i<=r; i++)

#define clr(x, c) memset(x, c, sizeof(x))

#define maxn 20

#define ll long long

#define l(x) x*2

#define r(x) x*2+1

using namespace std;

inline ll read()

{

	ll x=0, f=1; char ch=getchar();

	while (!isdigit(ch)) {if (ch=='-') f=-1; ch=getchar();}

	while (isdigit(ch)) x=x*10+ch-'0', ch=getchar();

	return x*f;

}

int n;

ll q;

ll m[maxn][maxn], m2[maxn][maxn], b[maxn], c[maxn], a[maxn], a2[maxn];

ll Query(ll k)

{

	if (k<=n) {ll now=0; rep(i, 1, k) now+=b[i]; return now;} else k-=n;

	clr(m, 0);

	rep(i, 1, n) m[n][n+1-i]=m[n+1][n+1-i]=c[i];

	rep(i, 1, n-1) m[i][i+1]=1; m[n+1][n+1]=1;

	rep(i, 1, n+1) a[i]=b[i];

	while (k)

	{

		if (k&1)

		{

			clr(a2, 0);

			rep(i, 1, n+1) rep(j, 1, n+1) a2[i]=(a2[i]+a[j]*m[i][j])%q;

			rep(i, 1, n+1) a[i]=a2[i];

		}

		clr(m2, 0);

		rep(i, 1, n+1) rep(j, 1, n+1) rep(o, 1, n+1) m2[i][j]=(m2[i][j]+m[i][o]*m[o][j])%q;

		rep(i, 1, n+1) rep(j, 1, n+1) m[i][j]=m2[i][j];

		k=k>>1;

	}

	return a[n+1];

}

int main()

{

	n=read();

	rep(i, 1, n) b[i]=read(), b[n+1]+=b[i];

	rep(i, 1, n) c[i]=read();

	ll x=read(), y=read(); q=read();

	rep(i, 1, n) b[i]%=q, c[i]%=q;

	printf("%lld", (Query(y)-Query(x-1)+2*q)%q);

	return 0;

}