102332: [AtCoder]ABC233 C - Product

Problem Statement

We have $N$ bags.
Bag $i$ contains $L_i$ balls. The $j$-th ball $(1\leq j\leq L_i)$ in Bag $i$ has a positive integer $a_{i,j}$ written on it.

We will pick out one ball from each bag.
How many ways are there to pick the balls so that the product of the numbers written on the picked balls is $X$?

Here, we distinguish all balls, even with the same numbers written on them.

Constraints

• $N \geq 2$
• $L_i \geq 2$
• The product of the numbers of balls in the bags is at most $10^5$: $\displaystyle\prod_{i=1}^{N}L_i \leq 10^5$.
• $1 \leq a_{i,j} \leq 10^9$
• $1 \leq X \leq 10^{18}$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $X$
$L_1$ $a_{1,1}$ $a_{1,2}$ $\ldots$ $a_{1,L_1}$
$L_2$ $a_{2,1}$ $a_{2,2}$ $\ldots$ $a_{2,L_2}$
$\vdots$
$L_N$ $a_{N,1}$ $a_{N,2}$ $\ldots$ $a_{N,L_N}$

Output

Print the answer.

Sample Input 1

2 40
3 1 8 4
2 10 5

Sample Output 1

2

When choosing the $3$-rd ball in Bag $1$ and $1$-st ball in Bag $2$, we have $a_{1,3} \times a_{2,1} = 4 \times 10 = 40$.
When choosing the $2$-nd ball in Bag $1$ and $2$-nd ball in Bag $2$, we have $a_{1,2} \times a_{2,2} = 8 \times 5 = 40$.
There are no other ways to make the product $40$, so the answer is $2$.

Sample Input 2

3 200
3 10 10 10
3 10 10 10
5 2 2 2 2 2

Sample Output 2

45

Note that we distinguish all balls, even with the same numbers written on them.

Sample Input 3

3 1000000000000000000
2 1000000000 1000000000
2 1000000000 1000000000
2 1000000000 1000000000

Sample Output 3

0

There may be no way to make the product $X$.

问题描述

我们有$N$个袋子。

第$i$个袋子包含$L_i$个球。第$i$个袋子的第$j$个球（$1\leq j\leq L_i$）上面写有一个正整数$a_{i,j}$。

我们需要从每个袋子中各挑出一个球。

有多少种方法可以在挑出的球上写的数的乘积为$X$？

注意，即使上面写的数相同，我们也要区分所有的球。

限制条件

• $N \geq 2$
• $L_i \geq 2$
• 袋子中球的数量的乘积不超过$10^5$：$\displaystyle\prod_{i=1}^{N}L_i \leq 10^5$。
• $1 \leq a_{i,j} \leq 10^9$
• $1 \leq X \leq 10^{18}$
• 输入中的所有值都是整数。

输入

从标准输入给出以下格式的输入：

$N$ $X$
$L_1$ $a_{1,1}$ $a_{1,2}$ $\ldots$ $a_{1,L_1}$
$L_2$ $a_{2,1}$ $a_{2,2}$ $\ldots$ $a_{2,L_2}$
$\vdots$
$L_N$ $a_{N,1}$ $a_{N,2}$ $\ldots$ $a_{N,L_N}$

输出

打印答案。

样例输入1

2 40
3 1 8 4
2 10 5

样例输出1

2

当从第1个袋子中选择第3个球和从第2个袋子中选择第1个球时，我们有$a_{1,3} \times a_{2,1} = 4 \times 10 = 40$。

当从第1个袋子中选择第2个球和从第2个袋子中选择第2个球时，我们有$a_{1,2} \times a_{2,2} = 8 \times 5 = 40$。

没有其他方法可以使乘积为40，所以答案是2。

样例输入2

3 200
3 10 10 10
3 10 10 10
5 2 2 2 2 2

样例输出2

45

注意，即使上面写的数相同，我们也要区分所有的球。

样例输入3

3 1000000000000000000
2 1000000000 1000000000
2 1000000000 1000000000
2 1000000000 1000000000

样例输出3

0

可能没有方法可以使乘积为$X$。