【BZOJ 4403】序列统计

链接

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4403
神犇题解：https://oi.men.ci/bzoj-4403/

题解

因为数定了，其单调不降的序列也就定了
所以这题就是求\(\sum\limits_{L = 1}^n {C_{r – l + L}^{r – l}} \)
然后化简一下就得到最终答案为：C(r-l+1,n+r-l+1)-1
ps：因为懒到不想写latex，所以化简过程让我们去膜拜Menci
因为n,l,r都巨大，所以用lucas定理来求组合数

Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N = 1000000+9;
const int MX = 1000000+2; 
const int MOD = 1000000+3;

int T,POW[N],REV[N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

inline int pow(int w, int t) {
	int ret = 1;
	while (t) {
		if (t & 1) ret = (LL)ret * w % MOD;
		w = (LL)w * w % MOD; t >>= 1;
	}
	return ret;
}

inline void prework() {
	POW[0] = REV[0] = 1;
	for (int i=1;i<=MX;i++) 
		POW[i] = (LL)POW[i-1] * i % MOD;
	REV[MX] = pow(POW[MX], MOD - 2);
	for (int i=MX-1;i;i--) 
		REV[i] = (LL)REV[i+1] * (i+1) % MOD;
}

int C(int a, int b) {
	if (a > b) return 0;
	else if (b <= MX) {
		return (LL)POW[b] * REV[a] * REV[b-a] % MOD;
	} else {
		return (LL)C(a%MOD, b%MOD) * C(a/MOD, b/MOD) % MOD;
	}
}

int main(){
	prework();
	for (int T=read(),n,l,r;T;T--) {
		n = read(); l = read(); r = read();
		printf("%d\n",(C(r-l+1,n+r-l+1)-1+MOD)%MOD);
	}
	return 0;
}