【题意】
给定三个正整数 \(N\)、\(L\) 和 \(R\)，统计长度在 \(1\) 到 \(N\) 之间，元素大小都在 \(L\) 到 \(R\) 之间的单调不降序列的数量。
输出答案对 \(10^6\!+\!3\) 取模的结果。
【样例输入】
2
1 4 5
2 4 5
【样例输出】
2
5
【题解】
首先，非常巧妙的
在求单调不降区间时，我们可以将第 \(i\) 位上的数 \(+i\)
将其转换为求单调上升序列，权值范围变成了 \([l+1,r+n]\)，一共有 \(n+r-l\) 个数，求取出 \(n\) 个数有多少方案
如果选 \(i\) 个数，它可以取的数的个数就是 \(C^{i}_{r-l+i}\)
设 \(M=r-l+1\)
所以我们要求所有长度的方案数就是
\[\begin{align}&\ \ \ \!\ \ \sum\limits^{n}_{i=1}C^i_{M+i-1}\\&=\sum\limits^{n}_{i=1}C^{M-1}_{M+i-1}\\&=\sum\limits^{n}_{i=1}C^{M-1}_{M+i-1}+C^{M}_{M}-1\\&=\sum\limits^{n}_{i=2}C^{M-1}_{M+i-1}+C^{M-1}_{M}+C^{M}_{M}-1\\&=\sum\limits^{n}_{i=2}C^{M-1}_{M+i-1}+C^{M}_{M+1}-1\\&=\sum\limits^{n}_{i=3}C^{M-1}_{M+i-1}+C^{M}_{M+2}-1\\&=C^{M}_{M+n}-1\\&=C^{r-l+1}_{n+r-l+1}-1\end{align}
\]
然后，由于 \(n\) 较大，我们用 Lucas 定理求组合数就好了，awa
代码如下：
#include<bits/stdc++.h>
#define rint register int
using namespace std;
inline int read(){
int s=0,f=1;char c=getchar();
while(c<'0'||c>'9'){if(c=='-')f=0;c=getchar();}
while(c>='0'&&c<='9')s=(s<<1)+(s<<3)+c-48,c=getchar();
return f?s:-s;
}
const int Mod=1e6+3;
int power(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%Mod;
}
int n,l,r;
int fac[1000010],inv[1000010];
int C(int n,int m){
if(m>n) return 0;
return 1ll*fac[n]*inv[n-m]%Mod*inv[m]%Mod;
}
int Lucas(int n,int m){
if(n<m) return 0;
if(m==0) return 1;
if(n<Mod&&m<Mod) return C(n,m);
return 1LL*Lucas(n/Mod,m/Mod)*C(n%Mod,m%Mod)%Mod;
}
int main(){
freopen("seq.in","r",stdin);
freopen("seq.out","w",stdout);
fac[1]=1; inv[0]=fac[0]=1;
for(rint i=2;i<Mod;++i) fac[i]=1ll*fac[i-1]*i%Mod;
inv[Mod-1]=power(fac[Mod-1],Mod-2);
for(rint i=Mod-1;i>1;--i) inv[i-1]=1ll*inv[i]*i%Mod;
int T=read();
while(T--){
n=read(); l=read(); r=read();
printf("%d\n",(Lucas(n+r-l+1,n)-1+Mod)%Mod);
}
return 0;
}