Medium
You are given two positive integers n and k.
A valid sequence is a sequence of k positive integers such that:
n.Return the number of valid sequences. Since the answer may be very large, return it modulo 109 + 7.
Two sequences are considered different if they differ at any index. For example, [1, 1, 2] and [1, 2, 1] are considered different sequences.
Example 1:
Input: n = 5, k = 3
Output: 3
Explanation:
The sequences of length k = 3 whose sum is 5 are:
| Sequence | Product | Parity |
|---|---|---|
[1, 1, 3] |
1 * 1 * 3 = 3 |
Odd |
[1, 2, 2] |
1 * 2 * 2 = 4 |
Even |
[2, 1, 2] |
2 * 1 * 2 = 4 |
Even |
[2, 2, 1] |
2 * 2 * 1 = 4 |
Even |
[1, 3, 1] |
1 * 3 * 1 = 3 |
Odd |
[3, 1, 1] |
3 * 1 * 1 = 3 |
Odd |
There are 3 sequences with an even product, thus the answer is 3.
Example 2:
Input: n = 3, k = 2
Output: 2
Explanation:
The sequences of length k = 2 whose sum is 3 are:
| Sequence | Product | Parity |
|---|---|---|
[1, 2] |
1 * 2 = 2 |
Even |
[2, 1] |
2 * 1 = 2 |
Even |
There are 2 sequences with an even product, thus the answer is 2.
Example 3:
Input: n = 5, k = 5
Output: 0
Explanation:
The only possible sequence of length k = 5 whose sum is 5 is [1, 1, 1, 1, 1], which has an odd product. Thus, the answer is 0.
Constraints:
1 <= n <= 5 * 1051 <= k <= npublic class Solution {
private static final int MOD = 1000000007;
private long power(long b, long e) {
long r = 1;
for (; e > 0; e >>= 1, b = b * b % MOD) {
if ((e & 1) == 1) {
r = r * b % MOD;
}
}
return r;
}
private long comb(int n, int k) {
if (k < 0 || k > n) {
return 0;
}
k = Math.min(k, n - k);
long res = 1;
long den = 1;
for (int i = 1; i <= k; ++i) {
res = res * (n - i + 1) % MOD;
den = den * i % MOD;
}
return res * power(den, MOD - 2L) % MOD;
}
public int countValidSequences(int n, int k) {
long res = comb(n - 1, k - 1);
if (n % 2 == k % 2) {
res = (res - comb((n + k) / 2 - 1, k - 1) + MOD) % MOD;
}
return (int) res;
}
}