4403: 序列统计

Time Limit: 3 Sec  Memory Limit: 128 MB

Submit: 858  Solved: 413

[][][]

Description

给定三个正整数N、L和R，统计长度在1到N之间，元素大小都在L到R之间的单调不降序列的数量。输出答案对10^6+3取模的结果。

Input

输入第一行包含一个整数T，表示数据组数。

第2到第T+1行每行包含三个整数N、L和R，N、L和R的意义如题所述。

1≤N,L,R≤10^9，1≤T≤100，输入数据保证L≤R。

Output

输出包含T行，每行有一个数字，表示你所求出的答案对10^6+3取模的结果。

Sample Input

2

1 4 5

2 4 5

Sample Output

2

5

//【样例说明】满足条件的2个序列为[4]和[5]。

HINT

 

Source

 

令M=r-l+1

根据多重集合的组合公式

ans= Σ C（M-1，i+M-1）  i∈[1,n]

然后 通过公式

C（M，M-1）=C（M+1，M）-1

C（M，N）= C（M-1，N）+ C（M-1，N-1）

可 化简 得 ans= C（M+N，M）-1

             

#include
      
       using namespace std;typedef long long LL;const int p=1e6+3;LL f[p+1];void pre(){    f[0]=1;    for(int i=1;i<=p;i++) f[i]=f[i-1]*i%p;}int pow(LL a,int b){    LL r=1;    while(b)    {        if(b&1) r*=a,r%=p;        b>>=1; a*=a; a%=p;    }    return r;}int C(int n,int m){    if(m>n) return 0;    return f[n]*pow(f[m]*f[n-m]%p,p-2)%p;}int Lucas(int n,int m){    LL ans=1;    for(;m;n/=p,m/=p) ans=ans*C(n%p,m%p)%p;    return ans;}int main(){    int T,n,l,r;    pre();    scanf("%d",&T);    while(T--)    {        scanf("%d%d%d",&n,&l,&r);        printf("%d\n",(Lucas(r-l+1+n,r-l+1)-1+p)%p);    } }