传送门

发现组合数有些有意思的式子要背证，哪天写个总结吧。

还现学了卢卡斯。

设$m=r-l$，则值域为$[l,r]$的方案数和$[0,m]$的方案数一样。

考虑长度为$n$的单调不降序列有多少种：

可以从$[0,m]$中取$n$个数（每个数可以重复取），升序排序就能得到一种方案。

也就是可重复组合$C_{m+n}^n$

答案就是$\sum\limits_{i=1}^nC_{m+i}^i$

然后通过百度发现$C$有这么个性质：

$\sum\limits_{i=0}^nC_{m+i}^i=C_{m+n+1}^n$

简单证一下：

$C_m^0+C_{m+1}^1+C_{m+2}^2+…+C_{m+n}^n$$

$=C_{m+1}^0+C_{m+1}^1+C_{m+2}^2+…+C_{m+n}^n$

$=C_{m+2}^1+C_{m+2}^2+…+C_{m+n}^n$

$=C_{m+n}^{n-1}+C_{m+n}^n$

$=C_{m+n+1}^n$

答案就成了$C_{m+n+1}^n-1$。

套个卢卡斯就行了。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cmath>
#include <cstring>

#define maxn 1005
#define inf 0x3f3f3f3f

const int mod = 1e6 + 3;

using namespace std;

inline int read(){
    int x=0,y=0;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')y=1;ch=getchar();}
    while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
    return y?-x:x;
}
int fac[mod]={1},inv[mod];
int INV(int x){return x==1?1:1ll*(mod-mod/x)*INV(mod%x)%mod;}
int C(int n,int m){
    if(n<m)return 0;
    if(n>=mod||m>=mod)return 1ll*C(n/mod,m/mod)*C(n%mod,m%mod)%mod;
    return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;
}
int main(){
    for(register int i=1;i<mod;++i)fac[i]=1ll*fac[i-1]*i%mod;
    inv[mod-1]=INV(fac[mod-1]);
    for(register int i=mod-2;~i;--i)inv[i]=1ll*inv[i+1]*(i+1)%mod;
    int t=read(),n,l,m;
    while(t--){
        n=read(),l=read(),m=read()-l;
        printf("%d\n",(C(m+n+1,n)-1+mod)%mod);
    }
}