感觉几百年没有刷bzoj了？虽然昨天才写了题，下午也还交了题的。
还是挺水的一道矩阵题。看到数列想得到矩阵，不知道没看到数列能不能想到矩阵。
关键是求和比较不好想。其实新加一行把和记下来就行了。重点就是构造对吧。
然后矩阵快速幂啥的还好。主要是要记得快速乘。（想起了zhx的babysit）
#include <iostream>
#ifndef ONLINE_JUDGE
#include <fstream>
#define cin _cin_
std :: ifstream cin("in.txt");
#endif
#include <algorithm>
using namespace std;
typedef long long qw;
const int maxn = 19;
qw n, b[maxn], c[maxn], x, y, mod;
qw modMul(qw a, qw b) {
qw s = 0;
for (; b; b >>= 1, a = (a << 1) % mod)
if (b & 1)
s = (s + a) % mod;
return s;
}
class matrix {
public:
int n;
qw a[maxn][maxn];
matrix(int n0) {
n = n0;
for (int i = 0; i < n; ++ i)
for (int j = 0; j < n; ++ j)
a[i][j] = (i == j);
}
matrix(int n0, qw v0) {
n = n0;
for (int i = 0; i < n; ++ i)
for (int j = 0; j < n; ++ j)
a[i][j] = v0;
}
void operator =(const matrix& x) {
n = x. n;
for (int i = 0; i < n; ++ i)
for (int j = 0; j < n; ++ j)
a[i][j] = x. a[i][j];
}
matrix operator *(const matrix& x) {
matrix s(n, 0);
for (int i = 0; i < n; ++ i)
for (int j = 0; j < n; ++ j)
for (int k = 0; k < n; ++ k)
s. a[i][j] = (s. a[i][j] + modMul(a[i][k], x. a[k][j])) % mod;
return s;
}
};
qw sov(qw x) {
if (x <= n) {
qw s = 0;
for (int i = 1; i <= x; ++ i)
s = (s + b[i]) % mod;
return s;
}
else {
qw t = 0;
matrix a(n + 1, 0), s(n + 1);
a. a[0][0] = 1;
for (int i = 1; i <= n; ++ i) {
a. a[0][i] = c[i];
a. a[1][i] = c[i];
if (i > 1)
a. a[i][i - 1] = 1;
}
for (x -= n; x; x >>= 1, a = a * a)
if (x & 1)
s = s * a;
for (int i = 1; i <= n; ++ i)
t = (t + b[i] + modMul(b[n - i + 1], s. a[0][i])) % mod;
return t;
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; ++ i)
cin >> b[i];
for (int i = 1; i <= n; ++ i)
cin >> c[i];
cin >> x >> y >> mod;
cout << (sov(y) - sov(x - 1) + mod) % mod << endl;
}