4403: 序列统计

题目连接：

http://www.lydsy.com/JudgeOnline/problem.php?id=4403

Description

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

Input

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

Output

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

Sample Input

2

1 4 5

2 4 5

Sample Output

2

5

Hint

提示

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

【数据规模和约定】对于100%的数据，1≤N,L,R≤10^9，1≤T≤100，输入数据保证L≤R。

题意

题解：

mdzz，样例没有换行符……

大水题，考虑长度为i的，大小为m的，那么能够构成的不降子序列的方案数位C(i+m-1,m-1)

然后sigma一下

发现答案就是C(i+m,m)-1

代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e6+3;

const int mod = 1e6+3;

long long fac[maxn];

long long qpow(long long a,long long b)

{

    long long ans=1;a%=mod;

    for(long long i=b;i;i>>=1,a=a*a%mod)

        if(i&1)ans=ans*a%mod;

    return ans;

}

long long C(long long n,long long m)

{

    if(m>n||m<0)return 0;

    long long s1=fac[n],s2=fac[n-m]*fac[m]%mod;

    return s1*qpow(s2,mod-2)%mod;

}

long long lucas(long long n,long long m)

{

    long long res=1;

    while(n||m)

    {

        res=res*C(n%mod,m%mod)%mod;

        n/=mod,m/=mod;

    }

    return res;

}

int main()

{

    fac[0]=1;

    for(int i=1;i<maxn;i++)

        fac[i]=fac[i-1]*i%mod;

    int t;scanf("%d",&t);

    while(t--)

    {

        int x,y,z;scanf("%d%d%d",&x,&y,&z);y=z-y+1;

        printf("%lld\n",(lucas(x+y,y)-1+mod)%mod);

    }

}