$\huge \color{orange}{成魔之路->}$ $\huge \color{purple}{算法提高课题解}$

思路：

$L\le a_1\le a_2\le … \le a_k\le R$

$差分映射：x_1+x_2+…+x_k\le R-L，其中\ x_i\ge 0$

$令\ y_i=x_i+1，则\ y_1+y_2+…+y_k\le R-L+k，其中\ y_i>0$

$隔板法（最后一个板子后面的元素不要选）：C_{R-L+k}^{k}$

$\begin{aligned}\sum\limits_{k=1}^NC_{R-L+k}^{k}& = \sum\limits_{k=1}^NC_{R-L+k}^{R-L} \\\\ & = C_{R-L+1}^{R-L}+C_{R-L+2}^{R-L}+…+C_{R-L+N}^{R-L}\\\\&=C_{R-L+1}^{R-L+1}+C_{R-L+1}^{R-L}+C_{R-L+2}^{R-L}+…+C_{R-L+N}^{R-L}-1\\\\&=C_{R-L+N+1}^{R-L+1}-1\end{aligned}$

$最后运用\ Lucas\ 定理求解\ C_{R-L+N+1}^{R-L+1}-1$

完整代码

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

const int p = 1e6 + 3;

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

int C(int a,int b)
{
    if(a<b) return 0;

    int up=1,down=1;
    for(int i=a,j=1;j<=b;i--,j++)
    {
        up=(LL)up*i%p;
        down=(LL)down*j%p;
    }

    return (LL)up*qmi(down,p-2,p)%p;
}

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

int main()
{
    int T;
    cin>>T;
    while(T--)
    {
        int n,l,r;
        cin>>n>>l>>r;
        cout<<(Lucas(r-l+n+1,r-l+1)+p-1)%p<<endl;
    }

    return 0;
}