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 <= nimport kotlin.math.min
class Solution {
private fun power(b: Long, e: Long): Long {
var b = b
var e = e
var r: Long = 1
while (e > 0) {
if ((e and 1L) == 1L) {
r = r * b % MOD
}
e = e shr 1
b = b * b % MOD
}
return r
}
private fun comb(n: Int, k: Int): Long {
var k = k
if (k < 0 || k > n) {
return 0
}
k = min(k, n - k)
var res: Long = 1
var den: Long = 1
for (i in 1..k) {
res = res * (n - i + 1) % MOD
den = den * i % MOD
}
return res * power(den, MOD - 2L) % MOD
}
fun countValidSequences(n: Int, k: Int): Int {
var res = comb(n - 1, k - 1)
if (n % 2 == k % 2) {
res = (res - comb((n + k) / 2 - 1, k - 1) + MOD) % MOD
}
return res.toInt()
}
companion object {
private const val MOD = 1000000007
}
}