/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 300 点
問題文
N 個の袋があります。
袋 i には L_i 個のボールが入っていて、袋 i の j(1\leq j\leq L_i) 番目のボールには正の整数 a_{i,j} が書かれています。
それぞれの袋から 1 つずつボールを取り出します。
取り出したボールに書かれた数の総積が 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 になる取り出し方が 1 つも存在しないこともあります。
Score : 300 points
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.