[题解]HDU7047-Link with Balls

题意

给你两类盒子, 每类\(n\)个, 编号分别从\(1\)到\(n\).

​ 第一类: 可以从第\(i\)个盒子里拿出\(i\)的任意非负整数倍数个小球

​ 第二类: 可以从第\(i\)个盒子里拿出最少\(0\)个最多\(i\)个小球.

多组数据\((1 \leq t \leq 10^5)\), 每组数据给出\(1 \leq n,m \leq 10^6\), 求从这\(2n\)个盒子里拿出\(m\)个小球的方案数模\(1e9+7\).

题解

懒得从组合意义的角度考虑, 可以用生成函数去做.

第一类第\(i\)个盒子对应的生成函数是 \[ \sum_{j = 0}^{∞}x^{i\cdot j} \]

第二类对应的是 \[ \sum_{j = 0}^ix^i \]

那么答案即为: \[ [m](\prod_{i = 1}^{n}\sum_{j = 0}^{∞}x^{i\cdot j})\cdot(\prod_{i = 1}^{n}\sum_{j = 0}^ix^i) \\ =[m](\prod_{i = 1}^{n}\frac{1}{1 - x^i})\cdot(\prod_{i = 1}^{n}\frac{1-x^{i+1}}{1-x})\\ =[m]\frac{1-x^{n+1}}{(1-x)^{n+1}}\\ =[m](1-x^{n+1})\cdot \sum_{i = 0}^{∞}C_{n+i}^ix^i\\ = C_{n+m}^m - C_{m-1}^{n} \]