三个条件同时满足的方案数不好求。容易发现,如果只满足前两个条件,方案数可以容易 DP 求出。那容斥减去其中不符合第三个条件的即可。
求解所有满足前两个条件的方案总数的 DP 很显然:设 $dp_1[i][j]$ 表示前 $i$ 种方法做了 $j$ 种菜的方案数,由条件 $2$ 知可以把方法作为阶段来递推,根据计数原理,简单拆一下求和号可知:
$dp_1[i][j] = dp_1[i-1][j] + \sum_{k=1}^{m} dp_1[i-1][j-1] \times a[i][k] = dp_1[i-1][j] + dp_1[i-1][j-1] \times \sum a[i]$
其中 $\sum a[i]$ 可以预处理出来,初始状态为 $dp_1[0][0] = 1$,满足前两个条件的总方案数是 $\sum dp_1[i][k]$,整个状态 + 转移时间复杂度 $O(nm)$。
接下来考虑如何求出应该减去的不符合条件 $3$ 的方案数。设用第 $x$ 种食材做了 $y_x$ 道菜,总共做了 $k$ 道菜。则除第 $x$ 种食材之外做了 $t_x = k-y_x$ 道菜。则不满足条件三等价于:$y_x > \lfloor \frac{k}{2} \rfloor$,整理可得 $y_x - t_x > 0$。
所以,重新定义状态:$dp[k][i][j]$ 表示用前 $i$ 中方法烹饪,第 $k$ 种菜满足 $y_k - t_k = j$ 的方案数。
分三类进行状态转移来计算状态 $dp[k][i][j]$:
- 不使用方法 $i$,这一部分对状态的贡献为 $dp[k][i-1][j]$。
- 使用方法 $i$ 烹饪一道第 $k$ 种菜,这一部分对状态的贡献为 $dp[k][i-1][j-1] \times a[i][k]$。
- 使用方法 $i$ 烹饪一道别的菜,这一部分对状态的贡献为 $dp[k][i-1][j+1] \times ( \sum a[i] - a[i][k])$
对于每个 $k$ 分别以 $i$ 为阶段递推计算即可。