题目链接:序列统计

  首先，L与R实际上是没太大意义的，因为我们需要的只是L和R之间含有多少个数，即R-L+1个数。其次，要注意一点，在一个序列中，数字是可以重复的。以样例中的2 4 5为例，符合要求的序列有{4},{5},{4,5},{4,4},{5,5}。事实上，问题可以转化为“有R-L+1个不同的盒子，若要将i(1<=i<=n)个相同的小球放进这些盒子里(某些盒子可以为空)，问对于所有的i，放法的总和是多少？”其中，不同的盒子代表着不同的数，在一个盒子中放入一个球，相当于选取一次该数字作为序列中的成员。再将问题抽象一下，即为“将i个小球划分成k堆(1<=k<=i)，问对于所有的i，划分方法的总和是多少？”对于这个问题，我们可以直接用C(m+n,n)求解(对于本题是C(seg+n,n),seg=R-L+1)另外，通过观察可知(其实是我不会推导。。。。。。),通过C(m+n,n)求出的数会比正确答案大1，故最终答案为C(seg+n,n)-1。 又因为10^6+3为素数，故可以用Lucas。

代码如下:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef long long ll;
ll fpow(ll a,ll b,ll p)
{
    ll ans=1;a%=p;
    while(b)
    {
        if(b&1)
            ans=(ans*a)%p;
        a=(a*a)%p;
        b>>=1;
    }
    return ans;
}
ll inv(ll x,ll p)
{
    return fpow(x,p-2,p);
}
ll comb(ll n,ll m,ll p)
{
    if(n<m)        return 0;
    ll up=1;ll down=1;
    for(int i=n-m+1;i<=n;i++)        up=(up*i)%p;
    for(int i=1;i<=m;i++)        down=(down*i)%p;
    return up*inv(down,p)%p;
}
ll lucas(ll a,ll b,ll p)
{
    return !b?1:lucas(a/p,b/p,p)*comb(a%p,b%p,p)%p;
}
int main()
{
    int t;
    ll n,lef,rig;
    ll p=3+1e6;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%lld %lld %lld",&n,&lef,&rig);
        ll seg=rig-lef+1;
        ll ans=0; 
        ans=(lucas(seg+n,n,p)+p-1)%p;
        printf("%lld\n",ans); 
    }
    return 0;
}