首页 > 代码库 > 【BZOJ4403】序列统计(Lucas定理,组合计数)
【BZOJ4403】序列统计(Lucas定理,组合计数)
题意:给定三个正整数N、L和R,
统计长度在1到N之间,元素大小都在L到R之间的单调不降序列的数量。
输出答案对10^6+3取模的结果。
对于100%的数据,1≤N,L,R≤10^9,1≤T≤100,输入数据保证L≤R。
题意:WYZ作业
L和R本身没有意义,等价于[1,R-L+1],共有R-L+1种取值方法
显然是一个阶梯状的东西
但我们直接算需要枚举长度,通分又很麻烦
考虑使用R-L填充长度不足N的区间,这样问题就转化为:
求长度为N,元素大小都在1到R-L之间的单调不降序列的数量
需要注意的是如果全部由R-L填充,则这个方案不合法,所以需要-1
ANS=C(n+R-L+1,n)-1
因为n+R-L较大,模数又是较小的指数,所以可以使用lucas定理
C(n,m)=C(n div mo,m div mo)*C(n mod mo,m mod mo) mod mo
1 const mo=1000003; 2 var fac,exf:array[0..mo]of int64; 3 cas,i,v,n,l,r:longint; 4 ans:int64; 5 6 function c(n,m:longint):int64; 7 begin 8 if n<m then exit(0); 9 if (n<mo)and(m<mo) then exit(fac[n]*exf[m] mod mo*exf[n-m] mod mo); 10 exit(c(n mod mo,m mod mo)*c(n div mo,m div mo) mod mo); 11 end; 12 13 begin 14 assign(input,‘bzoj4403.in‘); reset(input); 15 assign(output,‘bzoj4403.out‘); rewrite(output); 16 read(cas); 17 exf[0]:=1; exf[1]:=1; fac[0]:=1; 18 for i:=2 to mo do exf[i]:=exf[mo mod i]*(mo-mo div i) mod mo; 19 for i:=1 to mo do exf[i]:=exf[i-1]*exf[i] mod mo; 20 for i:=1 to mo do fac[i]:=fac[i-1]*i mod mo; 21 for v:=1 to cas do 22 begin 23 read(n,l,r); 24 ans:=c(n+r-l+1,n)-1; 25 ans:=(ans+mo) mod mo; 26 writeln(ans); 27 end; 28 close(input); 29 close(output); 30 end.
【BZOJ4403】序列统计(Lucas定理,组合计数)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。