laekov

感觉几百年没有刷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;

}