链接描述
这道题有点非人。
可以一点一点的做出来。
1.32ptsptspts做法-暴力搜索：
注意到前八个测试点n≤10n\le10n≤10，m≤3m\le3m≤3。
是可以使用DFS的数据范围。
顺便提一下题意：她会做ai,ja_{i,j}ai,j 道不同的使用方法iii和主要食材jjj的菜。
然后就是思考如何使用DFS了。
因为Rin的要求是每道菜的烹饪方式互不相同，所以在DFS的过程中可以将参数xxx设为使用的烹饪方式。
然后对于每种烹饪方式，选择一种主要食材，然后在最后进行一些操作。
错误的代码：
正确的代码：
正确的对比错误的，主要改了这几个点：
首先在check()check()check()函数的第二个forforfor循环中，当vis[i]vis[i]vis[i]等于零时，是需要先跳过的，不然之前的全都会清零。
其次，sumsumsum的取余应该放在里面。ansansans也应该取余。
接着第二个forforfor循环当中的sumsumsum的计算应该是乘法而不是加法。
因为有ai,ja_{i,j}ai,j 种使用iii烹饪方式和jjj个主要食材的菜。
所以最终方案数应该是乘在一起产生xxx种排饭方式，具体可以参考排列组合。
然后就是64pts64pts64pts的暴力DP。
是这样的：可以建立一个四维DP数组：dp[45][45][45][45]dp[45][45][45][45]dp[45][45][45][45]。
通过某些观察发现前十六个点都拥有m≤3m\le3m≤3的测试数据。
也就是说，只有3种主要食材。
dp[i][x][y][z]dp[i][x][y][z]dp[i][x][y][z]表示使用了前iii种烹饪方式，做了xxx道使用了第一种主要食材的菜，做了yyy道使用了第二种主要食材的菜，做了zzz道使用了第三种主要食材的菜的方案数。
思考一下状态转移方程：
第一种：不做任何菜f[i][x][y][z]+=f[i−1][x][y][z]f[i][x][y][z]+=f[i-1][x][y][z]f[i][x][y][z]+=f[i−1][x][y][z]
第二种：做第一种食材的菜f[i][x][y][z]+=f[i−1][x−1][y][z]∗a[i][1]f[i][x][y][z]+=f[i-1][x-1][y][z]*a[i][1]f[i][x][y][z]+=f[i−1][x−1][y][z]∗a[i][1]
第三种：做第二种食材的菜f[i][x][y][z]+=f[i−1][x][y−1][z]∗a[i][2]f[i][x][y][z]+=f[i-1][x][y-1][z]*a[i][2]f[i][x][y][z]+=f[i−1][x][y−1][z]∗a[i][2]
第四种：做第三种食材的菜f[i][x][y][z]+=f[i−1][x][y][z−1]∗a[i][3]f[i][x][y][z]+=f[i-1][x][y][z-1]*a[i][3]f[i][x][y][z]+=f[i−1][x][y][z−1]∗a[i][3]
做完了一个神秘的四层循环后，你会得到一个完善的四维DP数组。
然后要做的就是在这些方案中剔除一些错误的，保留正确的。
判断的话就跟DFS的判断是差不多的。
这是错误代码：
这是正确的代码：
只有一个错误，就是dpdpdp数组要开longlonglonglonglonglong。
因为在四维DP和数组A相乘的过程中，可能会爆intintint。
然后就是84pts84pts84pts的做法。
注意到（注意力惊人）对于每一种方案，其实我们只关心使用最多的食材和其他食材总数，所以我们可以尝试钦定主要食材。
注意：最多1个食材会超过使用食材的一半。
所以，可以将四维DP简化成这样:dp[45][405][405]dp[45][405][405]dp[45][405][405]。
dp[i][x][y]dp[i][x][y]dp[i][x][y]的状态表示是在有iii种烹饪方式，选中的主要食材kkk有xxx个，其他主要食材的数量为yyy的方案数。
这个状态表示有点怪怪的，因为有一个不表示在下标中的变量：kkk。
所以说，你可能需要循环nnn次去进行一个三维的循环，不过还好。
因为在前21个测试点中，有n≤40n\le40n≤40的限制。
所以其实不会超时。
再考虑一下它的状态转移方程：
1.不做新的菜：dp[i][x][y]+=dp[i−1][x][y]dp[i][x][y]+=dp[i-1][x][y]dp[i][x][y]+=dp[i−1][x][y]
2.做kkk号食材的菜：dp[i][x][y]+=dp[i−1][x−1][y]∗a[i][k]dp[i][x][y]+=dp[i-1][x-1][y]*a[i][k]dp[i][x][y]+=dp[i−1][x−1][y]∗a[i][k]
3.做其他食材的菜：dp[i][x][y]+=dp[i−1][x][y−1]∗(∑j=1ma[i][j]−a[i][k])dp[i][x][y]+=dp[i-1][x][y-1]* (\sum_{j = 1}^{m} a[i][j]-a[i][k])dp[i][x][y]+=dp[i−1][x][y−1]∗(∑j=1m a[i][j]−a[i][k])。
注释：
其实这种方法到最后求的不是“满足条件的方案数”而是将所有可能的方案全部算出后，再去求“不满足条件的方案数”
然后就可以开始写一些神秘的代码。
终于，要写100pts100pts100pts的代码了。
经过观察返现最后的几个测试点的范围是m≤2000m\le2000m≤2000。
这代表我们开不了三维数组。
时间复杂度方面也无法支撑。
这里就需要提一提DP的优化方法了。（其实前面就应该提了，忘了）。
DP的时间复杂度组成：O(状态∗转移)O(状态*转移)O(状态∗转移)。
那么优化自然也有两类优化：
1.优化状态：可以将两维做差值，压缩成一维（这种方法相当常见，除了本题，相似的还有那个前几天的括号序列）。
2.优化转移：优化转移的方法有很多，可以使用一些普及组算法，比如这道题就使用了前缀和。
那么现在要将84pts84pts84pts的做法优化成100pts100pts100pts的做法，考虑继续使用优化状态。
其实观察可发现，在这道题中，我们并不关心主要食材和其他食材具体有多少个。
我们只是希望通过知道它们的个数，从而得出它们相差几个，会不会不满足条件。
那么逻辑慢慢清晰。
我们将后两维优化成一维的差值。
也就是说现在是这样的：dp[i][j[dp[i][j[dp[i][j[表示有前iii种烹饪方式，主要食材-其他食材的个数是jjj。
但是问题在于，如何设计状态转移方程？
可以参考前几种做法的状态转移方程。
大概是这样：
1.不做：dp[i][j]+=dp[i−1][j]dp[i][j]+=dp[i-1][j]dp[i][j]+=dp[i−1][j]。
2.做主要食材的菜：dp[i][j]+=dp[i−1][j−1]∗a[i][k]dp[i][j]+=dp[i-1][j-1]*a[i][k]dp[i][j]+=dp[i−1][j−1]∗a[i][k]。
kkk是主要食材编号。
3.做其他食材的菜：dp[i][j]+=dp[i−1][j+1]∗(sum[i]−a[i][k])dp[i][j]+=dp[i-1][j+1]*(sum[i]-a[i][k])dp[i][j]+=dp[i−1][j+1]∗(sum[i]−a[i][k])。
然后需要注意一个问题：有没有一张可能，主要食材的数量≤\le≤其他食材的数量。
那么也就是说，j≤0j\le0j≤0。
（虽然说这种情况肯定不会算在“不满足条件”的方案数种）但是，想要求出“不满足条件”的方案数，是需要知道这些情况的数量的。
此时有一个聪明又机智的方法：
直接将jjj加上2000.（2000来源于mmm的范围）。
然后，在计算“不满足条件的方案数”的时候，就去计算大于2000的jjj的数量即可。
差不多了，代码跟84的差不多，甚至更简单。
有问题的代码：
正确的代码：
其实这两段代码只改了一个地方：
就是在solve()solve()solve()函数中，两层循环里的第一行代码：
错误的：
正确的：
注意：多次使用的函数就像多测一样，需要重新初始化。
如果不进行初始化，你的计算可能就会多一点注意事项。
