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

}