Connection Status:
Competition Arena > PowerPartition

PowerPartition

SRM 669 · 2015-08-31 · by sigma425

SRM 669 · 2015-08-31 · by sigma425 · Dynamic Programming
Class Name: PowerPartition
Return Type: int
Method Name: count
Arg Types: (int, long long)
Problem Statement

Problem Statement

Yayoi and Iori like traveling together. One day, they arrived to a strange planet. The currency system on the planet is really simple: the denominations are precisely all nonnegative powers of an integer M. I.e., the coins have the following values: 1, M, M^2, M^3, ...

Yayoi and Iori now want to buy souvenirs for their friends. The total price of those souvenirs is X. Yayoi and Iori would like to pay this amount exactly. They have a sufficient supply of coins with each of the available values.

You are given the int M and the long X. Let W be the number of different ways in which they can pay the required amount. Here, two ways are considered different if and only if there is some value such that in each way we use a different number of coins with this value. As W can be huge, return the value (W modulo 1,000,000,007).

Constraints

  • M will be between 2 and 1000, inclusive.
  • X will be between 1 and 10^18, inclusive.
Examples
0)
2
4
Returns: 4

The coins have values 1, 2, 4, 8, 16, etc. The amount Yayoi and Iori want to pay is 4. There are four different ways to do that: 4, 2+2, 2+1+1, and 1+1+1+1.

1)
17
1
Returns: 1

The price of souvenirs is only 1. There is only one way to pay this amount: by using a single coin with value 1.

2)
1000
1000000007
Returns: 500501002
3)
841
765346961765346961
Returns: 89045497
4)
2
1
Returns: 1

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

Coding Area

Language: C++17 · define a public class PowerPartition with a public method int count(int M, long long X) · 63 test cases · 2 s / 256 MB per case

Submitting as anonymous