#1942. 矩形
矩形
矩形
题目描述
标题: 矩形 - Problem - QOJ.ac
#13620. 矩形
The problem was used in the following contests:
本题中约定 00=1。
Snuke 使用动态规划解决了一道题目。具体来说,她设计了如下递推式:
F(i,j)={0,if i=0;fi,if i>0 and j=0;aF(i−1,j)+bF(i,j−1)+c,if i>0 and j>0.
其中 i,j 是非负整数,a,b,c 是给定的常数,fi 是给定的数列。
Snuke 需要求出 F(n,m),所以她对于 1≤i≤n,1≤j≤m 计算了 F(i,j),这些值形成了一个 n×m 的矩阵。
Takahashi 希望你告诉她这个矩阵。为了避免过多的输出,你只需要输出这个矩阵的哈希值。
具体来说,给定整数 h 和质数 p,你需要输出
(∑i=1n∑j=1mF(i,j)h(i−1)m+(j−1))modp
的值。
输入格式
从标准输入读入数据。
第一行输入一个整数 T,表示子任务编号。
第二行输入四个整数 n,m,h,p。
第三行输入三个整数 a,b,c。
第四行输入 n 个整数 f1,…,fn。
输出格式
输出到标准输出。
输出一行,包含一个整数,表示矩阵的哈希值。
样例一
input
1
2 2 2 998244353
2 1 1
0 1
output
93
explanation
题目描述中提到的矩阵是 (1249),其哈希值为
1×20+2×21+4×22+9×23=93.
样例二
input
2
9 100000 5 998244353
5 4 7
6 5 6 9 3 7 4 5 2
output
623270548
样例三
input
3
9 1000000000 5 235497281
5 0 7
6 5 6 9 3 7 4 5 2
output
211538270
限制及约定
对于所有数据,保证:
- 1≤n≤106
- 1≤m≤109
- 108≤p≤109,p 是质数
- 0≤h,a,b,c,fi<p
子任务编号n≤m≤特殊性质分值依赖的子任务110001000p=9982443535无21051052413106109b=010无4c=0285fi=0306无31, 2, 3, 4, 5
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
1
2 2 2 998244353
2 1 1
0 1
93
样例 2
2
9 100000 5 998244353
5 4 7
6 5 6 9 3 7 4 5 2
623270548