感谢 番茄酱 大佬排版精美的分享，本人下面分享中有摘选其文中段落，然后对部分地方加入了一些本人的看法，如有本人有描述失误的地方或大家不赞同的地方欢迎评论。✒️✒️✒️

分析

代码

#include<iostream>

using namespace std;

typedef long long LL;

const int p = 1e6+3;

int qmi(int a,int k){
    int res=1;
    while(k){
        if(k&1) res=(LL)res*a%p;
        a=(LL)a*a%p;
        k>>=1;
    }
    return res;
}

int c(int a,int b){
    /**按基础课的方式来写会超时，估计调用太多次qmi了*/
    // if(a<b) return 0;
    // int res=1;
    // //计算组合数公式:a*(a-1)*...*(a-b+1) / b!
    // for(int i=a,j=1;i>=a-b+1&&j<=b;i--,j++){
    //     res = (LL)res * i % p;
    //     //显然a,b是<p的数字，所以1~a,b之间的数字肯定都是和p互质的，所以可以用费马小定理求逆元
    //     res = (LL)res * qmi(j,p-2) % p;
    // }
    // return res;
    if(a<b) return 0;//不管为了正确性还是时间来说都请加上这句话
    int down=1,up=1;
    for(int i=a,j=1;j<=b;i--,j++){
        down=(LL)down*j%p;
        up=(LL)up*i%p;
    }
    return (LL)up*qmi(down,p-2)%p;

}

int lucas(int a,int b){
    if(a<p&&b<p) return c(a,b);
    return (LL)c(a%p,b%p)*lucas(a/p,b/p)%p;
}

int main(){
    int T;
    cin>>T;
    while(T--){
        int n,l,r;
        cin>>n>>l>>r;
        //把推导的公式用Lucas定理【a,b太大了】求一遍即可
        cout<<(LL)(lucas(r-l+n+1,r-l+1)-1 + p)%p<<endl;
    }

    return 0;
}

时间复杂度

即算T次Lucas定理的时间复杂度 $O(T \times plog_{2}n)$