bzoj 4403:シーケンス統計(Lucas定理)

タイトルの説明
トランスファゲート
3つの正の整数N、LとRを与えて、统计の长さは1からNの间で、元素の大きさはすべてLからRの间の単调な降伏しないシーケンスの数量です.10^6+3型取りの結果を出力します.
問題解
m=r-l+1とすると、私たちはm個の数に相当し、各数はxi個を選択し、最後の総和をNx 1+x 2+...+xm=Nにする.これは実際にはN個のボールをM個の箱に入れることに相当し、空の箱が現れることを許可する案数である.挿板法で答えを得るのは難しくないがC(N+m-1,m-1)では,この問題の答えはans=ΣNi=1 C(i+m−1,m−1)でt=m−1とし,ans=C(t+1,t)+C(t+2,t)+…+C(t+n,t)我々はC(t+1,t+1)を強引に加え,式を簡略化した.C(t+1,t)+C(t+1,t+1)=C(t+2,t+1)であることが判明し,その後,1項ずつ後方にマージし,最後にC(t+n+1,t+1)を得ると,答えはC(t+n+1,t+1)−C(t+1,t+1)=C(t+n+1,t+1)−1である.
コード#コード#

#include
#include
#include
#include
#include
#define LL long long 
#define p 1000003
#define N 2000000
using namespace std;
int jc[N],inv[N];
int T,n,l,r,m;
int quickpow(LL num,int x)
{
    LL base=num%p; LL ans=1;
    while (x){
        if (x&1) ans=ans*base%p;
        x>>=1;
        base=base*base%p;
    }
    return (int)ans;
}
LL C(LL n,LL m)
{
    if (m>n) return 0;
    return (LL)jc[n]*quickpow(jc[m],p-2)%p*quickpow(jc[n-m],p-2)%p;
}
LL calc(LL n,LL m)
{
    if (m==0) return 1;
    return calc(n/p,m/p)*C(n%p,m%p)%p;
}
int main()
{
    freopen("a.in","r",stdin);
    scanf("%d",&T);
    jc[0]=1;
    for (int i=1;i<=p;i++) jc[i]=(LL)jc[i-1]*i%p;
    //for (int i=0;i<=p;i++) inv[i]=quickpow(jc[i],p-2);
    while (T--) {
        scanf("%d%d%d",&n,&l,&r);
        m=(r-l+1)-1;
        //cout<
        LL ans=calc(m+n+1,m+1)-1;
        ans=(ans%p+p)%p;
        printf("%lld
",ans);
    }
}