4403: 序列统计
Time Limit: 3 Sec Memory Limit: 128 MBSubmit: 94 Solved: 39
[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
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。
Source
利用可重复的组合，可以推得方案数为C（n，n+r-l+1）-1。然后就用一下lucas定理就可以了。
附：lucas定理：C(m,n)%p=C(m/p,n/p)*C(m%p,n%p)。
代码：
#include<cstdio>
#define mod 1000003
using namespace std;
typedef long long ll;
int T;
ll n,L,R,fac[1000010];
ll ksm(ll x,ll y)
{
ll ans=1;
while (y)
{
if (y%2) ans=ans*x%mod;
x=x*x%mod;
y/=2;
}
return ans;
}
ll c(ll m,ll n)
{
if (n<m) return 0;
ll ans=fac[n];
ans=ans*ksm(fac[m],mod-2)%mod;
ans=ans*ksm(fac[n-m],mod-2)%mod;
return ans;
}
ll lucas(ll m,ll n)
{
if (!m) return 1;
return lucas(m/mod,n/mod)*c(m%mod,n%mod);
}
int main()
{
scanf("%d",&T);
fac[0]=1;
for (int i=1;i<=mod;i++) fac[i]=fac[i-1]*i%mod;
while (T--)
{
scanf("%lld%lld%lld",&n,&L,&R);
printf("%lld\n",(lucas(n,n+R-L+1)+mod-1)%mod);
}
}
评论 (0)
