首页 > 代码库 > bzoj 4403 序列统计
bzoj 4403 序列统计
4403: 序列统计
Time Limit: 3 Sec Memory Limit: 128 MBSubmit: 858 Solved: 413
[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的意义如题所述。
1≤N,L,R≤10^9，1≤T≤100，输入数据保证L≤R。
Output
输出包含T行，每行有一个数字，表示你所求出的答案对10^6+3取模的结果。
Sample Input
2
1 4 5
2 4 5
1 4 5
2 4 5
Sample Output
2
5
//【样例说明】满足条件的2个序列为[4]和[5]。
5
//【样例说明】满足条件的2个序列为[4]和[5]。
HINT
Source
By yts1999
令M=r-l+1
根据多重集合的组合公式
ans= Σ C（M-1，i+M-1） i∈[1,n]
然后 通过公式
C（M，M-1）=C（M+1，M）-1
C（M，N）= C（M-1，N）+ C（M-1，N-1）
可 化简 得 ans= C（M+N，M）-1
#include<cstdio>using namespace std;typedef long long LL;const int p=1e6+3;LL f[p+1];void pre(){ f[0]=1; for(int i=1;i<=p;i++) f[i]=f[i-1]*i%p;}int pow(LL a,int b){ LL r=1; while(b) { if(b&1) r*=a,r%=p; b>>=1; a*=a; a%=p; } return r;}int C(int n,int m){ if(m>n) return 0; return f[n]*pow(f[m]*f[n-m]%p,p-2)%p;}int Lucas(int n,int m){ LL ans=1; for(;m;n/=p,m/=p) ans=ans*C(n%p,m%p)%p; return ans;}int main(){ int T,n,l,r; pre(); scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&l,&r); printf("%d\n",(Lucas(r-l+1+n,r-l+1)-1+p)%p); } }
bzoj 4403 序列统计
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。