今天模拟赛的题目，赛时 84pts。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
题意解析：宋亦然会做很多菜，她掌握了 nnn 种烹饪方法，她还有 mmm 种主要食材。求符合以下要求的方案数：
* 做的菜的数量大于等于 111。
* 做的每道菜烹饪方法均不相同。
* 记做的菜的数量为 ttt，则同一种主要食材不能使用超过 ⌊t2⌋\lfloor\frac{t}{2}\rfloor⌊2t ⌋ 次。
64PTS
由于需要烹饪方法不同，所以考虑枚举烹饪方法，对菜进行选择。
我们用 dp[i][j][k][l]dp[i][j][k][l]dp[i][j][k][l] 记录前 iii 个烹饪方法，出现了 jjj 个主要食材 111，kkk 个主要食材 222，lll 个主要食材 333 的方案数。
转移方程挺好写的，枚举烹饪方法后再枚举食材即可。
时间复杂度 O(nm+1)O(n^{m+1})O(nm+1)，空间复杂度 O(nm+1)O(n^{m+1})O(nm+1)。
84PTS
按照上面的方法没什么前途了，不妨正难则反，先求出不考虑条件三的总情况数，再求出违反条件三的情况即可。
注意到如果违反条件三，则使用最多的食材的使用次数一定大于其他食材的使用次数。所以我们考虑按照这种方法 DP：
dp[i][j][k][l]dp[i][j][k][l]dp[i][j][k][l] 表示前 iii 个烹饪方法，第 jjj 种食材使用了 kkk 次，其他食材使用了 lll 次的方案数。状态转移方程如下：
dp[i][j][k][l]=dp[i−1][j][k−1][l]×Ai,j+dp[i−1][j][k][l−1]×((∑p=1mAi,p)−Ai,j)dp[i][j][k][l]=dp[i-1][j][k-1][l]\times A_{i,j}+dp[i-1][j][k][l-1]\times ((\sum_{p=1}^{m} A_{i,p})-A_{i,j}) dp[i][j][k][l]=dp[i−1][j][k−1][l]×Ai,j +dp[i−1][j][k][l−1]×((p=1∑m Ai,p )−Ai,j )
预处理出所有的 (∑p=1mAi,p)−Ai,j(\sum_{p=1}^{m} A_{i,p})-A_{i,j}(∑p=1m Ai,p )−Ai,j 即可。
当然，这样 DP 空间可能过大，所以应使用滚动数组减少一个维度。
时间复杂度 O(n3m)O(n^3m)O(n3m)，空间复杂度 O(n2m)O(n^2m)O(n2m)。
100PTS
模拟赛时时间不够没写出来。
注意到，我们只需要求所有 k>lk\gt lk>l 的状态数，不妨直接用 k−lk-lk−l 代替 k,lk,lk,l 两个数，此时我们只需要判断第三维是否大于 000 即可。
状态转移方程也就变成了：
dp[i][j][k]=dp[i−1][j][k−1]×Ai,j+dp[i−1][j][k+1]×((∑p=1mAi,p)−Ai,j)dp[i][j][k]=dp[i-1][j][k-1]\times A_{i,j}+dp[i-1][j][k+1]\times ((\sum_{p=1}^{m} A_{i,p})-A_{i,j}) dp[i][j][k]=dp[i−1][j][k−1]×Ai,j +dp[i−1][j][k+1]×((p=1∑m Ai,p )−Ai,j )
在实现的过程中，需要注意以下几点：
* k−lk-lk−l 可能会小于 000，所以应该加上偏移量 nnn。
* 依然要开滚动数组。
* 记得对 ∑Ai,j\sum A_{i,j}∑Ai,j 取模，不然会爆 long long！
时间复杂度 O(n2m)O(n^2m)O(n2m)，空间复杂度 O(nm)O(nm)O(nm)。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
Markdown:
