序列統計 lucas定理+組合數學

http://icpc.upc.edu.cn/problem.php?cid=1463&pid=41

:我們這個問題就直接相當于把”n個球放入m個盒子，盒子可以為空,球可以不選”，再減去n個球一個都不選的情況，那就直接是

了.

#include<cstdio>
#define p 1000003
#define ll long long
using namespace std;
ll f1[1000003],f2[1000003],m,n,t,l,r;
ll C(ll n,ll m)
{
    if (n<m)
        return 0;
    if (n<p&&m<p)
        return f2[n]*f1[m]%p*f1[n-m]%p;
    else
        return C(n/p,m/p)*C(n%p,m%p)%p;
}
int main()
{
    f2[0]=f1[0]=f2[1]=f1[1]=1;
    for (int i=2; i<p; i++)
    {
        f2[i]=(ll)f2[i-1]*i%p;
        f1[i]=(ll)(p-p/i)*f1[p%i]%p;
    }
    for (int i=2; i<p; i++)
        f1[i]=f1[i]*f1[i-1]%p;
    scanf("%lld",&t);
    while (t--)
    {
        scanf("%lld%lld%lld",&n,&l,&r);
        m=r-l+1;
        printf("%lld\n",(C(n+m,m)+p-1)%p);
    }
}