1023: 显像管

题目

题目描述

题目背景

身边再也没有所谓的“最重要之人”。

任凭时间一天天逝去，冲淡世界的色彩，荡涤内心那早已支离破碎的情感。

成为神明的话，就再也不怕孤身一人了吧。

至少我，一直这样坚定地认为着。

直到，那一天的到来。

创造世界，然后创造知性。

我所收到的要求，便是这样。

只是这样想着，便昏昏沉沉，坠入了梦乡。

在梦中，我见到了这样的一道题目:

题目描述

给定一个长度为 $n$ 的自然数数组 ${a_n}$，一个正整数 $L$，一个正整数 $M$。

有 $q$ 次询问，每次询问给定一个长度为 $L$ 的区间 $[l_i, r_i]$。对于每个询问，你需要输出下标在这段区间的 $a_i$ 的乘积，结果对 $M$ 取模。

输入格式

由于数据规模可能会很大，我们不会通过直接输入给出整个 ${a_n}$ 数组以及所有询问 。

输入只有一行五个数 $n, M, q, L, seed$。

你需要通过如下代码生成 ${a_n}$ 数组和询问。 ```cpp

include

using namespace std; const int maxn = 1e7 + 1e2; int a[maxn], l[maxn], r[maxn], n, m, q, L;

unsigned int seed; unsigned int xorshift() { seed ^= seed << 13; seed ^= seed >> 17; seed ^= seed << 5; return seed; } void generator() { for (int i = 1; i <= n; ++i) a[i] = xorshift() >> 1u; for (int i = 1; i <= q; ++i) r[i] = (l[i] = xorshift() % (n - L + 1) + 1) + L - 1; }

int main() { cin >> n >> m >> q >> L >> seed; generator(); //todo

return 0;

}

```

输出格式

$q$ 行，每行一个数表示答案。

样例输入

10 2333 3 5 123

样例输出

1658 1941 1069

数据范围

对于 40% 的数据，$1\leq n, q\leq 1000$

对于额外 10% 的数据，保证 $M$ 是质数

对于额外 20% 的数据，保证 $M$ 是两个不同质数的乘积

对于 100% 的数据，保证

$1\leq n \leq 10 ^ 7$

$1 \leq L \leq n$

$r_i - l_i + 1= L$

$M$ 在 int 范围内

Oops! 本题目还没有解答！

助教老师们编题的速度，已经超过了解题的速度！

OJ翻了一新，但本解答集还大多用的是2017-2019级，甚至更早的同学们贡献的答案。

如果你已经AC了，可以的话，请您参考添加页面，与大家一起分享你的题解！