Limits 10s, 512 MB

You have spent the last twenty years studying competitive programming. Now only one exam stands between you and becoming the very best. You open the exam paper and see a single problem.

You are given nn bags, each containing some distinct stones of varying weights. From each bag, you can pick at most one stone. You are also given a target fraction P/QP/Q. You have to pick stones so that their average weight is exactly P/QP/Q. How many ways can this be done so? Output the count of such ways.

Note that two ways of picking stones are different if there is some bag from which you pick a stone in one way but not in the other or if from some bag you pick different stone (different stones can have same weight).


First line of input will have a integer TT denoting the number of independent testcases.

Each testcase will start with a line containing one integer, nn denoting number of bags.

Next nn lines will contain the description of bags.

Each line will contain several space separated integers. They will start with an integer kk denoting the number of stones in the bag. Next kk integers will denote the weights of the stones in the bag. Final line of the testcase will contain two integers PP and QQ denoting the target fraction P/QP/Q.


  • 1T101 \leq T \leq 10

  • 1n1051 \leq n \leq 10^5

  • 1k991 \leq k \leq 99

  • 11\leq weight of each stone 109\leq 10^9

  • 1P,Q10181 \leq P, Q \leq 10^{18}

  • Product of (k+1)(k+1) over all bags in a testcase will be at most 101210^{12}


For each testcase output the count of ways in a single line.


2 1 1
2 1 1
1 1
2 2 3
3 1 4 2
3 3 2 1
5 2

In the first testcase, among the nine possible combinations of picking stones, one picks none of the stones and other eight picks stones in such a way that the average is exactly 1=111 = \frac 1 1.


Login to submit.


50% Solution Ratio
MinhazIbnMizanEarliest, 4M ago
MinhazIbnMizanFastest, 4.5s
MinhazIbnMizanLightest, 58 MB
MinhazIbnMizanShortest, 3956B
Toph uses cookies. By continuing you agree to our Cookie Policy.