这题难点就在于公式的推导
设k=r-l+1，那么我们相当于k个数，每个数选择xi个，使最后的总和为n
x1+x2+…+xk=n 这其实就相当于n个球放到k个盒子中，允许出现空盒子的方案数
ans=∑(i=1……n)C(i＋k,k)
可以利用杨辉三角，C(n,m)=C(n-1,m)+C(n-1,m-1);
ans=C(1+k,k)+C(2+k,k)+C(3+k,k)+……+C(n+k,k)
=C(1+k,1+k)-1+C(1+k,k)+C(2+k,k)+C(3+k,k)+……+C(n+k,k)
=(C(1+k,1+k)+C(1+k,k))+C(2+k,k)+C(3+k,k)+……+C(n+k,k)-1
=(C(2+k,1+k)+C(2+k,k))+C(3+k,k)+……+C(n+k,k)-1
=(C(3+k,1+k)+C(3+k,k))+……+C(n+k,k)-1
……
=C(n+k+1,k+1)-1
直接Lucas定理搞就可以了
lucas:C(n,m)%p=C(n/p,m/p)&C(n%p,m%p)
#include<iostream> #include<algorithm> 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]; long long 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; cin>>t; while(t--){ int x,y,z; cin>>x>>y>>z; y=z-y+1; cout<<(lucas(x+y,y)-1+mod)%mod<<endl; } } /* 2 1 4 5 2 4 5 */