#1942. 矩形

    ID: 1942 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest2398来源:qoj.ac数据:公开样例哈希动态规划模拟

矩形

矩形

题目描述

标题: 矩形 - Problem - QOJ.ac

#13620. 矩形

Statistics

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