#P1172. [Balkan2007]Dream

    ID: 179 传统题 1000ms 256MiB 尝试: 95 已通过: 47 难度: 6 上传者: 标签>CF2000提高线性 DP计数 DP欧几里得算法等价类划分预计算转移滚动数组

[Balkan2007]Dream

题目描述

给出 n 行 m 列的数字矩阵。从第一行的数列中选一个数字,从最后一行的数列中选一个数字。

从其它的行中,每行取一到两个数。将取出来的数字相乘,希望其可以被 k 整除。你只需要输出结果模 l 的值。

输入格式

第一行给出 n,m,第二行给出 k,l。下面有 n 行 m 列,用于描述数字矩阵。

输出格式

一行一个整数表示答案。

3 3
12 100
5 2 1
2 1 2
3 7 4
12

数据规模与约定

对于 100% 的数据,3≤n≤200,3≤m≤104,2≤k≤2×105,2≤l≤3×104,保证矩阵中所有的数都是 [1,106] 中的整数且互不相同。