题解 P5664 【Emiya 家今天的饭【民间数据】】

周子衡 · 2019-11-17 18:47:04 · 题解

又是趁着还没有题解，蒟蒻我来讲讲思路……

可以发现，从正面计算每种食材不超过一半的方案数比较困难，于是我们从反面考虑，总的方案数显然是(\prod_{i=1}^n(1+\sum_{j=1}^ma_{i,j}))-1（每种烹饪方式要么有一道菜要么一道也没有，减去什么都不选的一种），而要排除的方案数就是有至少一种食材超过一半的的方案数。

而又因为至多有一种食材超过一半，所以可以转化为：依次求出m种食材各自超过一半的方案数，然后一起减去。

很容易想到\text{DP}。记dp_{i,j,k,l}为在前i种烹饪方式中，选出k道菜，使得第j种食材恰有l次的方案数。易知

其中上式的三项分别为第i种烹饪方式什么也不选、选第j种食材、选除了第j种食材的其他食材，大家可以自行验证。记rs_i=\sum_{j=1}^ma_{i,j}，于是\sum_{1\leq j'\leq m,j'\neq j}a_{i,j'}=rs_i-a_{i,j}，上式转移可以在O(1)内实现，状态总数为O(n^3m)，故总时间复杂度为O(n^3m)。最后枚举j,k,l(2l>k)即可。得分84分。（出考场听到有84分我都震惊了）

考虑优化。鉴于转移是O(1)的，考虑优化状态。可以发现，如果要使第j种食材过半，等价于使第j种食材数量大于其他所有食材数量之和，而与上文的k,l无关。于是改进状态设计：

记dp_{i,j,k}表示在前i种烹饪方式中，使得第j种食材的数量减去其他食材的数量和的结果恰为k 的方案数（k可为负数，k\in [-n,n]）。可写出新的方程

其中上式的三项同样分别为第i种烹饪方式什么也不选、选第j种食材、选除了第j种食材的其他食材。上式转移同样可以在O(1)内实现，状态总数为O(n^2m)，故总时间复杂度为O(n^2m)。最后枚举所有j,k(k>0)即可。可以拿到满分。（貌似和上一个做法得分相差不大，可怜我白写了……）

代码蒟蒻我还没拿到，也懒得再打（其实是怕打错然后发慌），就不贴了。