P8XCoinChange

SRM 527 · 2011-05-25 · by dolphinigle

SRM 527 · 2011-05-25 · by dolphinigle · Dynamic Programming, Math

Show categories

Class Name: P8XCoinChange

Return Type: int

Method Name: solve

Arg Types: (long long, vector<long long>)

Problem Statement

The currency system in the Exponential Kingdom consists of various types of coins. The coin denominations follow these simple rules:

Each denomination is a positive integer.
There is a coin type with denomination 1.
For each pair of different coin types, the denomination of one coin type divides the denomination of the other one.

You are given a long[] values containing all the available denominations in ascending order. You are also given a long coins_sum. You want to pick a set of coins such that the sum of their values is exactly equal to coins_sum. Your method must count the number of ways in which such a set can be chosen. Since the answer may be very big, return it modulo 1,000,003 (10^6 + 3).

Notes

Let A and B be two sets of coins. They are considered different if and only if there exists a denomination X such that the numbers of coins worth X in A and in B differ.

Constraints

coins_sum will be between 1 and 10^18, inclusive.
values will contain between 1 and 40 elements, inclusive.
Each element of values will be between 1 and 10^18, inclusive.
values will be sorted in strictly ascending order. Note that this also implies that all the elements of values will be distinct.
For each pair of different elements in values, the smaller one will be a divisor of the larger one.
values[0] will be 1.

Examples

4
{1, 3}
Returns: 2

The two sets of coins with sum 4 are: {1, 1, 1, 1} {1, 3}

4
{1, 2, 4}
Returns: 4

The only possible set of coins that sums to 4 are: {1, 1, 1, 1} {1, 1, 2} {2, 2} {4}

3
{1, 5}
Returns: 1

11
{1, 2, 6}
Returns: 9

1000000000000000000
{1, 1000000000, 1000000000000000000}
Returns: 997005

There are exactly 1,000,000,002 possible sets, hence you should return 1,000,000,002 modulo 1,000,003 which is equal to 997,005.

892343554312566841
{1, 2048, 8192, 32768, 131072, 524288, 1048576, 4194304,
8388608, 33554432, 134217728, 536870912, 2147483648,
8589934592, 17179869184, 34359738368, 68719476736,
137438953472, 274877906944, 549755813888, 1099511627776,
2199023255552, 4398046511104, 8796093022208,
17592186044416, 35184372088832, 70368744177664,
140737488355328, 281474976710656, 562949953421312,
1125899906842624, 2251799813685248, 4503599627370496,
9007199254740992, 18014398509481984, 36028797018963968,
72057594037927936, 144115188075855872, 288230376151711744,
576460752303423488}
Returns: 386433

Please be careful with the time limit.

1000000000000000000
{1, 2048, 8192, 32768, 131072, 524288, 1048576, 4194304,
8388608, 134217728, 536870912, 2147483648,
8589934592, 17179869184, 34359738368, 68719476736,
137438953472, 274877906944, 549755813888, 1099511627776,
2199023255552, 4398046511104, 8796093022208,
17592186044416, 35184372088832, 70368744177664,
140737488355328, 562949953421312,
1125899906842624, 4503599627370496,
9007199254740992, 36028797018963968,
72057594037927936, 288230376151711744,
576460752303423488}
Returns: 461985

(for performance measuring purposes) number of elements in values = 35

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

Coding Area

Language: C++17 · define a public class P8XCoinChange with a public method int solve(long long coins_sum, vector<long long> values) · 275 test cases · 2 s / 256 MB per case