前置知识

排列组合 | 卢卡斯定理

解法

记 \(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;
}