#P18817. [Croatian CPC2015] Piramida
[Croatian CPC2015] Piramida
[Croatian CPC2015] Piramida
题目描述
Mirko 和 Slavko 在沙漠中发现了一座金字塔。门上的控制台给出了六个整数 ,用来生成一个具有 行的三角形数表。第 行有 个数,第 个数记为 。
数表按以下规则生成:
$$p(i,1)=\bigl(c\cdot p(i-1,1)\bigr)\bmod m\qquad(2\le i\le n),$$$$p(i,j)=\bigl(a\cdot p(i,j-1)+b\cdot p(i-1,j-1)\bigr)\bmod m \qquad(2\le i\le n,\ 2\le j\le i).$$
随后有 次询问。每次询问给出 ,表示顶端位于 、边长为 的子金字塔。它包含第 行中从第 个到第 个位置的数,其中 。
例如,图中红色边框表示 的子金字塔。
对于每次询问,请输出对应子金字塔中所有数的最大值。
输入格式
第一行包含六个整数 ,满足:
- ;
- ;
- 。
第二行包含一个整数 ()。
接下来 行,每行包含三个整数 ,满足 ,,。
输出格式
输出 行,每行一个整数,依次表示对应询问的答案。
样例 1
输入
3 1 1 1 1 3
2
1 1 1
1 1 2
输出
1
2
样例 2
输入
5 3 1 1 1 5
4
1 1 1
3 3 2
1 1 4
2 1 1
输出
3
4
4
3
样例 3
输入
34 72 111 13 17 912131
5
17 17 9
17 9 10
11 10 8
13 9 1
3 3 30
输出
877499
896373
838846
429006
911914
样例说明
样例 2 生成的数表为:
3
3 1
3 1 2
3 1 2 4
3 1 2 4 3
第二次询问的子金字塔包含 、 和 ,因此答案为 。