AT_abc233_c [ABC233C] Product

题目描述

有 $N$ 个袋子。
第 $i$ 个袋子中有 $L_i$ 个球，第 $i$ 个袋子的第 $j$ 个球上写有正整数 $a_{i,j}$，其中 $1 \leq j \leq L_i$。

从每个袋子中各取出一个球。
请问，有多少种取法，使得取出的球上所写数字的乘积恰好等于 $X$？

注意，即使数字相同，所有球也是互不相同的。

输入格式

输入按以下格式从标准输入给出。

$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

输出

2

样例 2

输入

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

输出

45

样例 3

输入

3 1000000000000000000
2 1000000000 1000000000
2 1000000000 1000000000
2 1000000000 1000000000

输出

0

说明/提示

限制条件

• $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}$
• 输入中所有数均为整数。

样例解释 1

选择袋子 $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

也有可能不存在任何一种取法使得乘积为 $X$。

由 ChatGPT 4.1 翻译