[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

sol

首先我们考虑一个这样的问题：把n个相同小球放在m个不同的盒子里的方案数。
因为盒子不同，所以不妨安排一个顺序。我们假设这些盒子是并排摆放的，那么每两个盒子之间就有一个隔板，总共有m-1个隔板。
其实问题就等同于：我有n+m-1个物品，我要在其中选出n个作为小球，其他的都是隔板，的方案数。
可见答案就是(C_{n+m-1}^{n})或是(C_{n+m-1}^{m-1})（是一样的）
发现这题惊人的一致：n个小球对应序列中n个元素，m个盒子对应可供选择的R-L+1个数。所以这题的答案就是(sum_{i=1}^{n}C_{i+m-1}^{m-1})
数学dalao告诉我们有一个这样的公式

[sum_{i=1}^{n}C_{m+i}^{m}=C_{n+m+1}^{m+1} ]

所以答案进一步化简为(C_{n+m}^{m})（其中(m=R-L+1)）
发现范围过大无法预处理阶乘，所以使用卢卡斯定理（(10^6+3)是个质数，别问我怎么知道的）

code

#include<cstdio>
#include<algorithm>
using namespace std;
const int mod = 1e6 + 3;
int jc[mod],inv[mod];
int gi()
{
	int x=0,w=1;char ch=getchar();
	while ((ch<'0'||ch>'9')&&ch!='-') ch=getchar();
	if (ch=='-') w=0,ch=getchar();
	while (ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
	return w?x:-x;
}
int fastpow(int a,int b)
{
	int res=1;
	while (b) {if (b&1) res=1ll*res*a%mod;a=1ll*a*a%mod;b>>=1;}
	return res;
}
int C(int m,int n)
{
	if (n<m) return 0;
	return 1ll*jc[n]*inv[m]%mod*inv[n-m]%mod;
}
int Lucas(int m,int n)
{
	if (m==0) return 1;
	return 1ll*Lucas(m/mod,n/mod)*C(m%mod,n%mod)%mod;
}
int main()
{
	jc[0]=inv[0]=1;
	for (int i=1;i<mod;i++) jc[i]=1ll*jc[i-1]*i%mod;
	inv[mod-1]=fastpow(jc[mod-1],mod-2);
	for (int i=mod-2;i;i--) inv[i]=1ll*inv[i+1]*(i+1)%mod;
	int T=gi();
	while (T--)
	{
		int n=gi(),L=gi(),R=gi(),m=R-L+1;
		printf("%d
",(Lucas(m,m+n)-1+mod)%mod);
	}
	return 0;
}