首页 > 代码库 > 【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定理,组合计数)