Solution - P5664 [CSP-S2019] Emiya 家今天的饭

P5664 [CSP-S2019] Emiya 家今天的饭

idea:

先容斥，将原问题转化为总方案减去不合法的方案。用乘法原理快速计算总方案，再寻找到一个漂亮的性质，利用 $dp$ 计算出不合法方案。 $dp$ 进行一步优化，减去无用状态。

简化题意：

有一个 $n$ 行 $m$ 列的矩阵，坐标为 $(i,j)$ 的格子上有 $a_{i,j}$ 个不同的数。

现在取 $k$ 个数满足以下条件：

1. $k>0$ 。

2. 每行只取一个数。

3. 每列最多取 $\lfloor\frac{k}{2}\rfloor$ 个数。

求方案数。

分析：

第三个条件不好下手，先不考虑。

我们不妨设 $s_i = \sum_{j=1}^m a_{i,j}$ 。

那么满足前两个条件的方案数显然是

$$\prod_{i=1}^n (s_i+1)\ \ - 1$$

可以 $O(n\cdot m)$ 处理出 $s_i$ ，再 $O(n)$ 求出。

接下来考虑第三个条件。

关键的思想：最多只有一列是不合法的 （即有 $2\cdot (\lfloor\frac{k}{2}\rfloor + 1) > k$ ）。

我们考虑枚举不合法的列。设当前枚举到了第 $i$ 行，不合法的列为 $k$ ，不合法的列选了 $j$ 个数，其他列选了 $h$ 个数。

设 $f_{k,i,j,h}$ 表示第 $k$ 列不合法，前 $i$ 行，不合法的列选了 $j$ 个数，其他列选了 $h$ 个数的方案数。有以下选择：

1. 在别的列取数：

$$f_{k,i-1,j,h-1}\cdot (s_i - a_{i,h})$$

2. 在不合法列取数：

$$f_{k,i-1,j-1,h}\cdot a_{i,h}$$

3. 当前行不取数：

$$f_{k,i-1,j,h}$$

故有转移：

$$f_{k,i,j,h} = f_{k,i-1,j,h-1}\cdot (s_i - a_{i,k}) + f_{k,i-1,j-1,h}\cdot a_{i,k} + f_{k,i-1,j,h}$$

不合法的方案数为：

$$\sum_{k=1}^m\sum_{j=1}^n \sum_{h=1}^{j-1} f_{n,j,h}$$

时间复杂度 $O(m\cdot n^3)$ ，可以拿高分。

然而我们发现，具体的 $j,h$ 对我们来说用处不大,我们只关心 $j-h$ 的值。

故可以将状态化为： $f_{k,i,j}$ 表示第 $k$ 列不合法，前 $i$ 行，不合法的列比其他列多选了 $j$ 个数的方案数。

显然 $j\in [-n,n]$ 。有转移：

$$f_{k,i,j} = f_{k,i-1,j+1}\cdot (s_i - a_{i,k}) + f_{k,i-1,j-1}\cdot a_{i,k} + f_{k,i-1,j}$$

时间复杂度 $O(m\cdot n^2)$ ，可以通过。