【BZOJ4403】序列统计（组合数学，卢卡斯定理）

题面

Description

给定三个正整数N、L和R，统计长度在1到N之间，元素大小都在L到R之间的单调不降序列的数量。输出答案对10^6+3取模的结果。

Input

输入第一行包含一个整数T，表示数据组数。

第2到第T+1行每行包含三个整数N、L和R，N、L和R的意义如题所述。

1≤N,L,R≤10^9，1≤T≤100，输入数据保证L≤R。

Output

输出包含T行，每行有一个数字，表示你所求出的答案对10^6+3取模的结果。

Sample Input

2

1 4 5

2 4 5

Sample Output

2

5

题解

\(L,R\)不就是搞笑的吗？

直接向左平移\(L-1\)个单位就好了。。。

以下的\(X=R-(L-1)\)

现在，认真的来解决问题

考虑这样一道小学奥数题：

有\(n\)个相同的小球，要放进\(m\)个不同的盒子里

每个盒子可以为空，求放的方案数

先给每个盒子人为的放一个小球

再用隔板法计算

答案为\(C_{n+m-1}^{m-1}\)

现在，这个问题不就是一样的吗？

相当于有X个盒子，分别代表着X个数字

现在有\(i\)个小球，求放法总数

其中\(i\in [1,n]\)

所以，所求为：

\(\sum_{i=1}^nC_{i+X-1}^{X-1}\)

化简一下

\(C_{n+X}^X-1\)

然后卢卡斯一波就可以啦

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define MOD 1000003

#define MAX (MOD+1000)

#define ll int

ll n,L,R;

ll jc[MAX],inv[MAX];

inline int read()

{

    int x=0,t=1;char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

ll fpow(ll a,ll b)

{

	ll s=1;

	while(b){if(b&1)s=1ll*s*a%MOD;a=1ll*a*a%MOD;b>>=1;}

	return s;

}

ll C(ll m,ll n)

{

	if(n<m)return 0;

	return 1ll*jc[n]*inv[m]%MOD*inv[n-m]%MOD;

}

ll Lucas(ll m,ll n)

{

	if(n<m)return 0;

	if(m==0)return 1;

	return (1ll*Lucas(m/MOD,n/MOD)*C(m%MOD,n%MOD))%MOD;

}

int main()

{

	int T;T=read();

	jc[0]=inv[0]=1;

	for(int i=1;i<MOD;++i)jc[i]=1ll*jc[i-1]*i%MOD;

	inv[MOD-1]=fpow(jc[MOD-1],MOD-2);

	for(int i=MOD-2;i;--i)inv[i]=1ll*inv[i+1]*(i+1)%MOD;

	while(T--)

	{

		n=read();L=read();R=read();

		R-=L-1;

		printf("%d\n",(Lucas(R,n+R)-1+MOD)%MOD);

	}

	return 0;

}