4403: 序列统计
Time Limit: 3 Sec Memory Limit: 128 MB
Submit: 328 Solved: 162
[Submit][Status][Discuss]
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
Sample Output
HINT
提示
【样例说明】满足条件的2个序列为[4]和[5]。
【数据规模和约定】对于100%的数据，1≤N,L,R≤10^9，1≤T≤100，输入数据保证L≤R。
Source
题解：
Lucas定理＋组合数学
公式推导见：http://blog.csdn.net/lych_cys/article/details/50616439
公式化简见：http://blog.csdn.net/popoqqq/article/details/50636866
化简：
设k=r-l;
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定理搞就可以了
注意输出要写 ((ans-1LL)%MOD+MOD)%MOD ，要不会WA(输出－1了)
#include<bits/stdc++.h>
using namespace std;
#define MOD 1000003
#define LL long long
LL jc[MOD+];
int read()
{
int s=,fh=;char ch=getchar();
while(ch<''||ch>''){if(ch=='-')fh=-;ch=getchar();}
while(ch>=''&&ch<=''){s=s*+(ch-'');ch=getchar();}
return s*fh;
}
LL ksm(LL bb,LL pp,LL kk)
{
LL s=1LL;
while(pp>0LL)
{
if(pp%2LL!=0LL)s=(s*bb)%kk;
pp/=2LL;
bb=(bb*bb)%kk;
}
return s;
}
LL C(int n,int m,int P)
{
if(m>n)return 0LL;
if(n-m<m)m=n-m;
return (jc[n]*ksm((jc[m]*jc[n-m])%P,P-,P))%P;
}
LL Lucas(int n,int m,int P)
{
if(m==)return 1LL;
return (C(n%P,m%P,P)*Lucas(n/P,m/P,P))%P;
}
void cljc()
{
jc[]=1LL;
for(int i=;i<=MOD;i++)jc[i]=(jc[i-]*i)%MOD;
}
int main()
{
int k,l,r,n,T;
LL ans;
cljc();
T=read();
while(T--)
{
n=read();l=read();r=read();
k=r-l;
ans=Lucas(k+n+,k+,MOD);
printf("%lld\n",((ans-1LL)%MOD+MOD)%MOD);
}
fclose(stdin);
fclose(stdout);
return ;
}