Connection Status:
Competition Arena > GoodSubset

GoodSubset

SRM 632 - TCO14 Wildcard Sweep · 2014-08-25 · by dreamoon

SRM 632 - TCO14 Wildcard Sweep · 2014-08-25 · by dreamoon · Dynamic Programming, Simple Math
Class Name: GoodSubset
Return Type: int
Method Name: numberOfSubsets
Arg Types: (int, vector<int>)
Problem Statement

Problem Statement

You have some cards, each containing a positive integer. You are given a int[] d. Each element of d is one of those integers. The integers are not necessarily distinct.

You are also given an int goodValue. You are interested in non-empty subsets of cards with the following property: The product of integers written on those cards is exactly equal to goodValue.

Let X be the number of subsets with the above property. Compute and return the value (X modulo 1,000,000,007).

Constraints

  • goodValue will be between 1 and 2,000,000,000, inclusive.
  • d will contain between 1 and 100 elements, inclusive.
  • Each element of d will be between 1 and 2,000,000,000, inclusive.
Examples
0)
10
{2,3,4,5}
Returns: 1

There is only one good subset:{2,5}.

1)
6
{2,3,4,5,6}
Returns: 2

There are two good subsets: {2,3} and {6}.

2)
1
{1,1,1}
Returns: 7

All non-empty subsets of this set of cards are good.

3)
12
{1,2,3,4,5,6,7,8,9,10,11,12}
Returns: 6
4)
5
{1,2,3,4}
Returns: 0

Submissions are judged against all 93 archived test cases, of which 5 are shown here. Case numbers match the judge’s.

Coding Area

Language: C++17 · define a public class GoodSubset with a public method int numberOfSubsets(int goodValue, vector<int> d) · 93 test cases · 2 s / 256 MB per case

Submitting as anonymous