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
2 3
3 3

2 3

3 3

4
2

不考虑同种物品之间的区别，一共有 \(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 …

分类：计数DP