首页 > 代码库 > Bzoj4403 序列统计
Bzoj4403 序列统计
Submit: 566 Solved: 270
[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
21 4 52 4 5
Sample Output
25
HINT
提示
【样例说明】满足条件的2个序列为[4]和[5]。
【数据规模和约定】对于100%的数据，1≤N,L,R≤10^9，1≤T≤100，输入数据保证L≤R。
Source
By yts1999
数学问题 组合数 lucas定理
设m=R-L+1，即可用的数值的数量
推一波公式,得到答案就是C(n+m,m)-1，用lucas定理算出来即可
蜜汁WA2次之后直接把int全开成LL，就蜜汁过了
1 /*by SilverN*/ 2 #include<algorithm> 3 #include<iostream> 4 #include<cstring> 5 #include<cstdio> 6 #include<cmath> 7 #include<vector> 8 #define LL long long 9 using namespace std;10 const int mod=1e6+3;11 const int mxn=1000010;12 int read(){13 int x=0,f=1;char ch=getchar();14 while(ch<‘0‘ || ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}15 while(ch>=‘0‘ && ch<=‘9‘){x=x*10+ch-‘0‘;ch=getchar();}16 return x*f;17 }18 LL pw[mxn],inv[mxn];19 void init(){20 pw[0]=1;inv[1]=1;21 pw[1]=1;inv[0]=1;22 for(int i=2;i<mxn;i++){23 pw[i]=(LL)pw[i-1]*i%mod;24 inv[i]=((-(mod/i)*(LL)inv[mod%i])%mod+mod)%mod;25 }26 return;27 }28 LL calc(int n,int m){29 if(n<m)return 0;30 int res=(LL)pw[n]*inv[pw[m]]%mod*inv[pw[n-m]]%mod;31 return res;32 }33 LL lucas(LL n,LL m){34 if(!m)return 1;35 return calc(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;36 }37 int T,n,m,L,R;38 int main(){39 int i,j;40 T=read();41 init();42 while(T--){43 n=read();L=read();R=read();44 m=R-L+1;45 int ans=lucas((LL)n+m,m)-1;46 if(ans<0)ans+=mod;47 printf("%d\n",ans);48 }49 return 0;50 }
Bzoj4403 序列统计
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。