「DPOI-1」炊事员的鸡汤 - 算法题解与代码 - 常规

题目描述

炊事员老冯有 $n$ 种配方瓶，其中对于一份第 $i$ 种配方，鸡汤和毒药分别有 $x_i, y_i$ 毫升。现在他需要用鸡汤和毒药配出最佳的配方，不能太明显也不能没有毒效。

现在你需要帮他调配鸡汤，具体地：

设 $a_i \geq 0$ 表示第 $i$ 中配方使用的份数。老冯必须使用整数份。
老冯希望 $a$ 单调不降。
老冯还希望鸡汤混合毒药后的净含量为 $m$ 毫升，即 $m = \displaystyle\sum_{i = 1}^n a_i (x_i + y_i)$。
老冯还希望鸡汤与毒药的质量比为 $o : p$，即 $\displaystyle\sum_{i = 1}^n a_i x_i : \displaystyle\sum_{i = 1}^n a_i y_i = o : p$。

请你快速求出有多少种满足条件的调配方案。由于结果可能很大，你只需要求出结果对 $10^9 + 7$ 取模的值。

样例

输入样例： 2 2 20 9 1 17 1 1 1 3 100 4 1 25 5 20 10 14 19 输出样例： 1 0

算法

(数学，高斯消元，线性代数) $O(n^3)$

~更好的阅读体验~

题解

这是一道比较有趣的数学题目。

首先，我们考虑 $o:p$ 的约束。我们将 $\displaystyle\sum_{i=1}^{n}a_ix_i$ 设为 $Ax$，$\displaystyle\sum_{i=1}^{n}a_iy_i$ 设为 $Ay$，那么 $Ax: Ay=o:p$ 等价于 $\begin{bmatrix}o & -p\end{bmatrix}\begin{bmatrix}Ax\Ay\end{bmatrix}=0$。这是一个 $1\times 2$ 的矩阵，可以用高斯消元求解。如果这个方程无解，那么直接输出 $0$，否则，我们将 $Ax$ 和 $Ay$ 的比值设为 $k$，即 $\dfrac{Ax}{Ay}=k$，那么 $Ax=kAy$。

接下来，我们考虑 $m$ 的约束。我们将 $\displaystyle\sum_{i=1}^{n}a_i(x_i+y_i)$ 设为 $S$，那么 $S=m$。

由于 $a$ 单调不降，所以我们可以发现，对于一个 $a$，如果 $a_i>0$，那么 $a_{i+1}$ 一定不为 $0$，否则 $a$ 不单调不降。所以我们可以将 $a$ 中所有 $0$ 去掉，假设 $a$ 剩下 $k$ 个元素，那么 $k\leq n$。

接下来，我们考虑如何求解 $a$ 的方案数。我们将 $a$ 拆分成若干组，每组的元素是相同的，假设有 $t$ 组，那么 $t\leq k$。我们将 $a$ 按照相同元素的个数排序，假设有 $l_1,l_2,\cdots,l_t$ 组，其中 $l_1\geq l_2\geq\cdots\geq l_t$。

对于一个 $a$，我们将它拆分成若干组，每组的元素是相同的，假设有 $t$ 组，那么 $t\leq k$。我们将 $a$ 按照相同元素的个数排序，假设有 $l_1,l_2,\cdots,l_t$ 组，其中 $l_1\geq l_2\geq\cdots\geq l_t$。对于每组，设它的元素为 $a_1,a_2,\cdots,a_{l_i}$，那么它们的和为 $s_i$，我们需要求解一个方程组：$$ \begin{cases} a_1+a_2+\cdots+a_{l_i}=s_i \ a_1\leq a_2\leq\cdots\leq a_{l_i} \end{cases} $$ 由于 $a$ 单调不降，所以我们可以用组合数求解上述方程组的方案数，即为 $\dbinom{s_i-1}{l_i-1}$。

最后，我们需要求解所有 $a$ 的方案数之和，即 $\sum\limits_{a\in A}\prod\limits_{i=1}^{t}\dbinom{s_i-1}{l_i-1}$，其中 $A$ 表示所有合法的 $a$。

我们可以将 $a$ 看作 $k$ 个小球，将它们放入 $t$ 个盒子中，由于每个盒子至少有一个球，所以我们可以先将 $k$ 个球放入 $t$ 个盒子中，然后将每个盒子中的一个球拿出来。这样，我们就得到了一个方案，假设第 $i$ 个盒子中有 $l_i$ 个球，那么这个方案的贡献为 $\dbinom{k-1}{l_1-1}\dbinom{k-l_1}{l_2-1}\cdots\dbinom{k-l_1-\cdots-l_{t-1}}{l_t-1}$。

我们将所有方案的贡献加起来，就得到了答案。

时间复杂度分析：$O(n^3)$，其中 $n$ 表示配方瓶的数量。

参考代码