DistinctRemainders
SRM 572 · 2012-12-13 · by fushar
SRM 572 · 2012-12-13 · by fushar · Dynamic Programming, Simple Math
Problem Statement
Problem Statement
You are interested in a sequence of integers S = (S[1], S[2], ..., S[K]) with the following properties:
You are given along N and an int M. Return the number of different valid sequences S, modulo 1,000,000,007. Two sequences S1 and S2 are considered different if they either have different number of elements, or if there is an index i such that S1[i] is different from S2[i].
- K >= 1.
- For all i, S[i] is a non-negative integer.
- S[1] + S[2] + ... + S[K] = N.
- S[1] mod M, S[2] mod M, ..., S[K] mod M are all different.
You are given a
Constraints
- N will be between 1 and 10^18, inclusive.
- M will be between 1 and 50, inclusive.
Examples
0)
3 2 Returns: 5
The 5 sequences are: (3) (0, 3) (1, 2) (2, 1) (3, 0)
1)
3 3 Returns: 9
The 9 sequences are: (3) (1, 2) (2, 1) (0, 1, 2) (0, 2, 1) (1, 0, 2) (1, 2, 0) (2, 0, 1) (2, 1, 0)
2)
58 1 Returns: 1
The only sequence is (58).
3)
572 7 Returns: 922572833
4)
1000000000000000000 20 Returns: 240297629
Watch out for overflows.
Submissions are judged against all 103 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class DistinctRemainders with a public method int howMany(long long N, int M) · 103 test cases · 2 s / 256 MB per case