前置知识
解法
记 \(m=r-l+1,0 \le k \le n-1\) ，枚举长度 \(i\) ，等价于求 \(\sum\limits_{j=1}^{m}x_j=i\) 的非负整数解的数量。接着推式子就行。
\(\begin{aligned} \sum\limits_{i=1}^{n}\dbinom{m+i-1}{i} \end{aligned}\)
\(\begin{aligned} &=\dbinom{m}{0}-1+\sum\limits_{i=1}^{n}\dbinom{m+i-1}{i} \end{aligned}\)
\(\begin{aligned} &=\dbinom{m}{1}+\dbinom{m}{0}-1+\sum\limits_{i=2}^{n}\dbinom{m+i-1}{i} \end{aligned}\)
\(\begin{aligned} &=\dbinom{m+1}{1}-1+\sum\limits_{i=2}^{n}\dbinom{m+i-1}{i} \end{aligned}\)
\(\begin{aligned} &=\dbinom{m+k}{k}-1+\sum\limits_{i=k+1}^{n}\dbinom{m+i-1}{i} \end{aligned}\)
\(\begin{aligned} &=\dbinom{m+n-1}{n-1}+\dbinom{m+n-1}{n}-1 \end{aligned}\)
\(\begin{aligned} &=\dbinom{n+m}{n}-1 \end{aligned}\)
因为 \(n,m\) 较大，所以需要跑卢卡斯定理。
代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define sort stable_sort
#define endl '\n'
ll inv[1000010],jc[1000010],jc_inv[1000010];
ll C(ll n,ll m,ll p)
{
if(n>=m&&n>=0&&m>=0)
{
return (jc[n]*jc_inv[m]%p)*jc_inv[n-m]%p;
}
else
{
return 0;
}
}
ll lucas(ll n,ll m,ll p)
{
return m?C(n%p,m%p,p)*lucas(n/p,m/p,p)%p:1;
}
int main()
{
ll t,n,m,l,r,i,p=1000003;
cin>>t;
inv[1]=1;
jc[0]=jc_inv[0]=jc[1]=jc_inv[1]=1;
for(i=2;i<=p-1;i++)
{
inv[i]=(p-p/i)*inv[p%i]%p;
jc[i]=jc[i-1]*i%p;
jc_inv[i]=jc_inv[i-1]*inv[i]%p;
}
for(i=1;i<=t;i++)
{
cin>>n>>l>>r;
m=r-l+1;
cout<<(lucas(n+m,n,p)+p-1)%p<<endl;
}
return 0;
}