题目分析

本题要求的是长度为$k$的数组数量，且这些数组需要保证：

1. 数组中数字总和为$n$；
2. 数组中数字乘积为偶数； 注意需将求出的数组数量对$10^9+7$取余后返回答案。

基本思路

DFS+记忆化搜索（超时）

分析题目可以发现，实际上这个数组中只需要保证至少有一个偶数，即可满足题目的第2个要求，因此可以用$DFS$进行填数字，最终判断所填的数字中是否有偶数出现，即可判定填出来的数组是否符合要求，具体$DFS$函数如下：

def dfs(pos, left, hasEven):
	if pos == k-1:
		return int(hasEven | (left%2==0))
	res = 0
	for i in range(1, left-(k-pos-1)+1):
		res = (res+dfs(pos+1, left-i, hasEven|(i%2==0)))%modNum
	return res

需要注意的是，在从左向右第$pos$位上填数字时，若在保证总和为$n$的前提下剩下数字的总和为$left$，那么为保证后面的位置还可以至少填1，当前所能填的最大数字只能是$left-(k-pos-1)$。

不过可惜的是，如此简洁优雅的代码只能通过369/803个测试用例，因此只能更换算法。

组合数计算

前置知识

现有一个问题如下：

已知一个列表长度为$a$，总和是$b$($a\leq b$)，且其中所有元素均为正整数，那么共有多少个该种列表？

为解决这个问题，可以这样考虑，如果有$b$个小球顺次排开，在所有缝隙之中插入$a-1$个挡板，只要保证没有两个挡板插在同一个缝隙，且没有挡板插在最左或最右边，那么即可将这$b$个小球分成$a$堆，同时满足每堆数量均为正整数。这样，将每一堆小球的数量组成一个列表，这就是一个符合要求的列表。

而$b$个小球中总共有$b-1$个空隙，现在又要插$a-1$个挡板，那么总共合规的情况数，即满足要求的列表数量即为：$C_{b-1}^{a-1}$.

可以发现，利用组合数其实可以很简单计算出来总情况数量，即$C_{n-1}^{k-1}$，那么如果能用同样的方式计算出来无效序列数目，两个相减即可得到有效序列数目了。

什么是无效序列数目呢？题目要求数组中所有数字的乘积是偶数时才表明该数组是有效序列，那么无效序列就是所有数字乘积为奇数的数组，这么看来，只有全部都是奇数的数组才是无效序列。下面来求全部都是奇数，且总和为$n$，长度为$k$的数组数量。

每一个奇数都可以表示为$2x_i - 1(x_i\geq 1)$，因此要求的实际上就是数列$[x_0, x_1, \dots, x_{k-1}]$的数量，且数列满足：

将求和式子展开后可得：

化简可得：

因此，问题就转换成了：求长度为$k$，总和为$\frac{n+k}{2}$且均为正整数的数列数量，和「前置知识」中的问题相同，注意到如果$n+k$是奇数，不可能有符合要求的任何数列，故可知，无效序列的总数为：

综上所述，即可得知有效序列的总数为：

求组合数即可用预处理阶乘加上公式计算即可。

复杂度

时间复杂度：$O(1)$ 空间复杂度：$O(1)$

代码

modNum = 1_000_000_007
maxNum = 500001
prod = [1]*maxNum
for i in range(1, maxNum):
    prod[i] = (prod[i-1]*i)%modNum

def myComb(m, n):
    return prod[m]*pow((prod[n]*prod[m-n])%modNum, -1, modNum)%modNum

class Solution:
    def countValidSequences(self, n: int, k: int) -> int:
        if n == k:
            return 0
        tot = myComb(n-1, k-1)
        odd = 0
        if (n-k)%2 == 0:
            odd = myComb((n-k)//2+k-1, k-1)
        return (tot-odd)%modNum