YZOJ P3033 背包

时间限制：1000MS      内存限制：131072KB

出题人：chj2001             难度：$5.4$

• 题目描述

存在 $n$ 种物品，其中第 $i$ 种物品的价值为 $a_i$ ，最多可以用 $b_i$ 件，求从这些物品中选取若干件（不能为 $0$ 件），得到的总价值为 $9$ 的倍数的方案。

需要分别计算每种物品中，每件之间有区别的方案数和没有区别的方案数。

（即每种物品按照 $1,2,3, \cdots ,b_i$ 编号的方案数和不编号的方案数。）

• 输入格式

第一行输入一个数 $n$ 。

接下来 $n$ 行，每行两个数 $a_i, b_i$ 。

• 输出格式

输出共两行，每行各包括一个数，分别表示对于每种物品视为不同的时的方案数和视为相同的时的方案数。有的时候方案数可能很大，你需要将它对 $10^9+7$ 取模。

方案数均不考虑顺序，如 $2, 3, 4$ 和 $4, 3, 2$ 是同一种方案。

如果无法做到则输出 $0$ 。

• 样例输入

• 样例输出

• 样例说明

不考虑同种物品之间的区别，一共有 $2$ 种不同的方案凑出 $9$ 的倍数，即 $3, 2, 2, 2$ 和 $3, 3, 3$ 。

考虑同种和果子的区别时，一共有 $C_3^1 \times C_3^3 = 3$ 种不同的方案凑出 $3, 2, 2, 2$，$C_3^3=1$ 种方案凑出 $3, 3, 3$，因此总共有 $4$ 种方案。

• 数据规模与约定

对于 $40\%$ 的数据，$n \le 1000 , a_i \le 100 , b_i \le 100$ 。

对于 $100\%$ 的数据，$1 \le n \le 10^5 , 1 \le a_i \le 90000 , 1 \le b_i \le 90000$

。

 

 

 

---

 

 

 

首先如果每种物品没有区别的话，那就是一个模意义下的计数背包问题，可以有：

$f_{i, j} = \sum\limits_{k=0}^{b_i}{f_{i-1, \left(j-k \times a_i\right) \% 9}}$ ，时间复杂度为 $O\left(9n\max\{b_i\}\right)$ 。

注意到 $\left(j-k \times a_i\right) \% 9$ 是有循环性的，所以分类合并一下就可以做到 $O\left(9^2n\right)$ 。

（代码大概是这个样子的：

 

现在问题是每种物品不同的方案数如何计算。

推一下式子会发现我们需要计算 $C_n^9 + C_n^{18} + C_n^{27} + \cdots$ ，这个东西。。。。。。

算了吧，OEIS 上都没有这个数列的线性计算方法。

考虑换一种思路，把每种物品都拆成 $b_i$ 件，然后考虑 DP 的转移。

把被动转移变成主动转移，那么一种物品的转移其实就是 $f_{i, j} \to f_{i+1, j},\ f_{i, j} \to f_{i+1, \left(j+a_i\right) \% 9}$。

注意到可以把这样的转移写成矩阵的形式，并且此矩阵为循环矩阵。

比如 $a_i=3$ ，那么有：

$\begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\  0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \end{bmatrix}$

并且注意到，在模 $9$ 意义下相同的 $a_i$ 的转移矩阵都是相同的，所以可以直接开一个桶 $cnt$ 表示此数量，并且转移使用矩阵快速幂即可。

循环矩阵的每一行都是上一行向左/右移动一位得到的，所以暴力乘法是 $O(9^2)$ 。

时间复杂度： $O\left(n+9^3\log \sum\limits_{i=1}^n b_i \right)$