NKOJ 3823 水果怪 （组合数）

发表于 |
字数统计: 551字 | 阅读时长 ≈ 3min

P3823水果怪

问题描述

小南和小开在三友路上养了很多只果冻怪。我们可以将三友路想象成一根长度无限的数 轴，在这上面生活着n只果冻怪。每经过一秒，一只果冻怪便会分裂成两只。具体来说，一 只坐标为x的果冻怪，会分裂成两只分别在(x − 1),(x + 1)上的果冻怪，并且原来在x上的果 冻怪会消失。 由于生存空间有限，若一个位置上有不少于P只果冻怪，那么会立刻消失 P 只。经过测 定P = 10^9 + 7。 小南和小开想知道在第T秒末，位置w有多少只果冻怪。初始时刻是0秒初。

输入格式

第一行为三个整数，n，T，w。含义如题所述。
接下来 n 行，每行两个整数xi,ci，表示xi位置，有ci只果冻怪。注意xi可能有重复。

输出格式

输出一个非负整数，表示 T 秒末 w 位置上的果冻怪个数

样例输入

2 2 2 
0 3 
1 2

样例输出

3

提示

对于 30%的数据： 1 ≤ n ≤ 100，1 ≤ T ≤ 16。
对于 60%的数据：1 ≤ n ≤ 10^5，1 ≤ T ≤ 16。
对于 100%的数据：1 ≤ n,T,ci ≤ 10^5,0 ≤ |w|,|xi| ≤ 10^5。

找找规律容易发现是组合数，然而此题需要求$C_{T}^{i}$，直接卢卡斯要超时，需要使用递推求解。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<stdio.h>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace  std;
ll p=1000000007,ans;
ll C[1234567];
ll QM(ll a,ll b)
{
	ll c=1;a=a%p;
	while(b)
	{
		if(b&1)c=c*a%p;
		b>>=1;
		a=a*a%p;
	}
	return c;
}
int main()
{
	ll i,n,T,w,x,c,d;
	scanf("%lld%lld%lld",&n,&T,&w);
	C[0]=1;
	for(i=1;i<=T;i++)C[i]=C[i-1]*(T-i+1)%p*QM(i,p-2)%p;
	for(i=1;i<=n;i++)
	{
		scanf("%lld%lld",&x,&c);
		if(w>x)d=w-x;
		else d=x-w;
		if((T&1)&&(d&1))ans=(ans+c*C[d/2+T/2+1]%p)%p;
		if((!(T&1))&&(!(d&1)))ans=(ans+c*C[d/2+T/2]%p)%p;
	}
	printf("%lld",ans);
}