TheCowDivOne
SRM 502 · 2010-11-01 · by rng_58
SRM 502 · 2010-11-01 · by rng_58 · Dynamic Programming, Math
Problem Statement
Problem Statement
Farmer John had N cows numbered 0 to N-1. One day he saw K cows running away from his farm. Fox Brus computed the sum of the numbers of the escaped cows. She only told John that the sum was divisible by N.
Your task is to help John by counting the number of possible sets of escaped cows. This number may be very big, so return it modulo 1,000,000,007.
Your task is to help John by counting the number of possible sets of escaped cows. This number may be very big, so return it modulo 1,000,000,007.
Constraints
- N will be between 1 and 1,000,000,000, inclusive.
- K will be between 1 and 1,000, inclusive.
- K will be less than or equal to N.
Examples
0)
7 4 Returns: 5
7 cows are numbered 0 to 6 and 4 of them run away. Possible sets of escaped cows are {0, 1, 2, 4}, {0, 3, 5, 6}, {1, 2, 5, 6}, {1, 3, 4, 6}, {2, 3, 4, 5}.
1)
1 1 Returns: 1
2)
58 4 Returns: 7322
3)
1000 47 Returns: 219736903
4)
1000000000 1000 Returns: 666683069
Submissions are judged against all 61 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class TheCowDivOne with a public method int find(int N, int K) · 61 test cases · 2 s / 256 MB per case