山东省第八届 ACM 省赛 fireworks （组合数+逆元）

山东省第八届 ACM 省赛 fireworks （组合数+逆元）

Description

Input

Input contains multiple test cases.For each test case:The first line contains 3 integers n,T,w(n,T,|w|≤10^5)In next n lines, each line contains two integers xi and ci, indicating there are ci fireworks in position xi at the beginning(ci,|xi|≤10^5).

Output

For each test case, you should output the answer MOD 1000000007.

Example Input

1 2 02 22 2 20 31 2

Example Output

23

题意

烟花在每秒都会分裂一次，并且分裂成的两半刚好落在相邻的两点，然后它们也可以继续分裂。

给出 ​​n​​​ 个点烟花的初始数量，问经过 ​​T​​​ 秒后在点 ​​w​​ 有多少数量的烟花。

思路

考虑所有的烟花分裂都是一样的，并且其分裂之后所形成的局势仅和时间有关。

所以我们只需要关心一个烟花是如何分裂的：

0 0 0 0 0 1 0 0 0 0 00 0 0 0 1 0 1 0 0 0 00 0 0 1 0 2 0 1 0 0 00 0 1 0 3 0 3 0 1 0 00 1 0 4 0 6 0 4 0 1 0

第几行代表第几秒，行中的每个数字代表当前时间该点烟花的数量，于是我们发现了一个中间插入了 ​​0​​ 的杨辉三角，计算方法也就是组合数咯~

从上面的矩阵我们可以发现，当时间与距离同奇偶的时候才处于杨辉三角中，其余情况都为 ​​0​​ 。

因为题目中数据比较大，所以计算组合数需要用到乘法逆元，先打表求出 ​​n!​​ ，然后根据组合数公式计算即可。

AC 代码

#include#include#include#include#include#includeusing namespace std;#include#include

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。