思路分析
如果我们希望直接解得这个情况数，似乎并不容易，因此考虑使用间接的求法。观察一下题目条件，要求合法的解满足这样三个条件
1. 菜数k≥1k \ge 1k≥1
2. 每种烹饪方式至多选择一次
3. 每种食材至多选择⌊k2⌋\lfloor \frac{k}{2} \rfloor⌊2k ⌋次
显然，其中最复杂的是3，那么我们可以考虑先求出所有仅满足1,2的情况，然后再去把不满足3的排除。
第一次DP，求满足1,2的情况
我们还是正常的思考，先想一个dp(i)dp(i)dp(i)表示选取前iii个烹饪法的有效菜品数，因为此时dp(i)dp(i)dp(i)似乎不只是受dp(i−1)dp(i-1)dp(i−1)的影响，还需要涉及之前的决策情况。所以这个时候，我们无法从dp(i−1)dp(i-1)dp(i−1)直接推出答案，需要引入一个新的信息，帮助我们求解。我们考虑引入一个表示目前已选取的烹饪法数jjj。因此我们定义为dp1(i,j)dp_1(i,j)dp1 (i,j)。
现在我们考虑转移的过程，对于每一步dp(i,j)dp(i,j)dp(i,j)。考虑两种决策
* 如果当前一步选择使用iii,则产生dp_1(i-1,j-1)\cdot \mbox{当前烹饪法可能产生选择数}种方案，其中当前烹饪法可能产生选择数我们可以用一个数组额外存储这一列的数字和，记作s(i)=∑j=1mai,js(i)=\sum_{j=1}^{m}a_{i,j}s(i)=∑j=1m ai,j .
* 如果当前一步不选择，那么还能继承上一步的情况数，即dp1(i−1,j−1)dp_1(i-1,j-1)dp1 (i−1,j−1)
综上得到这样一个转移方程 $$dp_1(i,j)=dp(i-1,j-1)+dp(i-1,j)\cdot s(i)$$
于是全部满足1,2的解可以在O(n2)O(n^2)O(n2)复杂度内被找到。
第二次DP，如何求不合法解数
要求不满足条件3的情况，我们可以发现,当某种食材ccc用了超过⌊k2⌋\lfloor \frac{k}{2}\rfloor⌊2k ⌋次，考虑极端情况，其使用了⌊k2⌋+1\lfloor \frac{k}{2}\rfloor+1⌊2k ⌋+1次，则其他食材的使用总次数为k−⌊k2⌋−1k-\lfloor \frac{k}{2}\rfloor-1k−⌊2k ⌋−1对于这个式子，考虑两种情况
* 如果kkk是奇数,设k=2n+1k=2n+1k=2n+1，则原式=2n+1−n−1=n=k−12=2n+1-n-1=n=\frac{k-1}{2}=2n+1−n−1=n=2k−1
* 如果kkk是偶数，设k=2nk=2nk=2n,原式=2n−n−1=n−1=2n-n-1=n-1=2n−n−1=n−1
因为k−1=2n−1k-1=2n-1k−1=2n−1
所以⌊k−12⌋=⌊n−0.5⌋=n−1=\lfloor \frac{k-1}{2}\rfloor=\lfloor n -0.5\rfloor =n-1=⌊2k−1 ⌋=⌊n−0.5⌋=n−1=原式
综上，我们可以得知此时其他食材的使用总次数是⌊k−12⌋≤⌊k2⌋\lfloor \frac{k-1}{2}\rfloor\le\lfloor\frac{k}{2}\rfloor⌊2k−1 ⌋≤⌊2k ⌋
那么显然，至多有一个食材会被过度使用。我们考虑枚举这个食材ccc
我们定义一个dpdpdp,继续先考虑dp(i)dp(i)dp(i)与之前一样。然而同样，我们也无法直接统计出dp(i)dp(i)dp(i)之前所有过度情况数，于是引入另一个参数。我们引入一个过度使用的食材ccc的参数，然后似乎还需要记录其使用次数和其他食材的种类和使用次数等信息。
这会造成不可接受的时间和空间复杂度，我们必须要思考如何消掉不必要的信息。
首先，关于当前删去哪个节点的信息是不必要的，
因为它不参与到状态转移的过程中，而仅仅只是被枚举考虑的量，并且我们的dpdpdp执行累加，并不会因为状态重叠这类的问题造成程序错误。因此我们可以正确的这样操作。同理，其余未被选择的食材数也只需要记录其数量即可，因为其他的信息不参与和影响转移。于是我们终于得到了较为简单的dp2(i,p,q)dp_2(i,p,q)dp2 (i,p,q)
我们简单推导一下转移方程
* 不选择第iii种烹饪方式并让被枚举到的ccc过度使用,情况数dp2(i−1,p,q)dp_2(i-1,p,q)dp2 (i−1,p,q)
* 选择第iii种烹饪方式，并让ccc过度使用（进一步的过度），情况数dp2(i−1,p−1,q)⋅ai,cdp_2(i-1,p-1,q)\cdot a_{i,c}dp2 (i−1,p−1,q)⋅ai,c
* 选择第iii种烹饪方式，但不选择ccc,产生情况数dp2(i−1,p,q−1)⋅(s(i)−ai,c)dp_2(i-1,p,q-1)\cdot (s(i)-a_{i,c})dp2 (i−1,p,q−1)⋅(s(i)−ai,c )
综上，可得dp2dp_2dp2 的转移方程为
dp2(i,p,q)=dp2(i−1,p,q)+dp2(i−1,p−1,q)⋅ai,c+dp2(i−1,p,q−1)⋅(s(i)−ai,c)dp_2(i,p,q)=dp_2(i-1,p,q)+dp_2(i-1,p-1,q)\cdot a_{i,c}+dp_2(i-1,p,q-1)\cdot (s(i)-a_{i,c}) dp2 (i,p,q)=dp2 (i−1,p,q)+dp2 (i−1,p−1,q)⋅ai,c +dp2 (i−1,p,q−1)⋅(s(i)−ai,c )
几乎完美，除了时间。这个算法的复杂度是O(mn3)O(mn^3)O(mn3)，仍超我们可以接受的范围
优化
不难发现，不合法的充分必要条件是p>qp>qp>q
::: proof
Proof. 当p>⌊k2⌋p>\lfloor \frac{k}{2} \rfloorp>⌊2k ⌋时
q=n−j<n−⌊k2⌋q=n-j<n-\lfloor \frac{k}{2} \rfloorq=n−j<n−⌊2k ⌋
类似于之前证明"仅有一个食材过度使用"的方法，可得k−⌊k2⌋≤pk-\lfloor \frac{k}{2} \rfloor\le pk−⌊2k ⌋≤p
故q<pq<pq<p,充分性得证
现在假设已有p>qp>qp>q
则p+q=kp+q=kp+q=k,2p>k2p>k2p>k,p>k2≥⌊k2⌋p>\frac{k}{2}\ge \lfloor \frac{k}{2} \rfloorp>2k ≥⌊2k ⌋
此时，情况不合法，必要性得证 ◻
:::
就这样，我们可以只考虑p−qp-qp−q,但是为了避免负索引造成的问题，我们再加上一个总食材数nnn，于是我们得到了降维的状态dp2(i,z)dp_2(i,z)dp2 (i,z)
dp2(i,z)=dp2(i−1,z−1)+dp2(i−1,z−1)⋅ai,c+dp2(i−1,z+1)⋅(s(i)−ai,c)dp_2(i,z)=dp_2(i-1,z-1)+dp_2(i-1,z-1)\cdot a_{i,c}+dp_2(i-1,z+1)\cdot (s(i)-a_{i,c}) dp2 (i,z)=dp2 (i−1,z−1)+dp2 (i−1,z−1)⋅ai,c +dp2 (i−1,z+1)⋅(s(i)−ai,c )
这样，我们的复杂度就只剩下了O(mn2)O(mn^2)O(mn2)，完美AC
代码实现
