1856: [Scoi2010]字符串

1856: [Scoi2010]字符串

Time Limit: 5 Sec  Memory Limit: 64 MB

Submit: 847  Solved: 434

[Submit][Status]

Description

lxhgww最近接到了一个生成字符串的任务,任务需要他把n个1和m个0组成字符串,但是任务还要求在组成的字符串中,在任意的前k个字符中,1的个数不能少于0的个数。现在lxhgww想要知道满足要求的字符串共有多少个,聪明的程序员们,你们能帮助他吗?

Input

输入数据是一行,包括2个数字n和m

Output

输出数据是一行,包括1个数字,表示满足要求的字符串数目,这个数可能会很大,只需输出这个数除以20100403的余数

Sample Input

2 2

Sample Output

2

HINT

【数据范围】 对于30%的数据,保证1<=m<=n<=1000 对于100%的数据,保证1<=m<=n<=1000000

Source

Day2

题解:这个题不难想——首先就是这种类似找钱问题的模型,便可以转化为一个方格然后走路的模型(类似于杨辉三角,传送门,这个链接里面有详细的讲解,再次不再赘述,此题Ans=C(m+n,n)-C(m+n,n+1))。。。紧接着——常年不写逆元的我(HansBug:首先连公式都快忘了 Phile:呵呵,不就是(a/b) mod p=(a*ksm(b,p-2)) mod p,其中p为质数,ksm(a,b)表示求a的b次幂,一般用快速幂写)又开始了逗比事业——先是先乘完了分母,然后再一个个的来逆元求商,呵呵呵呵。。。果断TLE,然后可爱的我才意识到貌似可以把分母乘起来再逆元,然后没有然后了(Phile:你为啥总是那么充满喜剧色彩= =  HansBug:唉。。要不谈何萌妹哪。。。)

 1 const p=20100403;
 2 var
 3    m,n:longint;
 4    i,j:int64;
 5 function ksm(x,y:longint):int64;inline;
 6          var
 7             z,i:int64;
 8          begin
 9               x:=x mod p;
10               z:=1;
11               i:=x;
12               while y>0 do
13                     begin
14                          if odd(y) then z:=(z*i) mod p;
15                          i:=(i*i) mod p;
16                          y:=y div 2;
17                     end;
18               ksm:=z;
19          end;
20 function cc(x,y:longint):int64;inline;
21          var
22             i:longint;z,z2:int64;
23          begin
24               z:=1;
25               if y>(x div 2) then y:=x-y;
26               i:=x;
27               while i>=(y+1) do
28                     begin
29                          z:=(z*i) mod p;
30                          dec(i);
31                     end;
32               i:=x-y;z2:=1;
33               while i>=1 do
34                     begin
35                          z2:=(z2*i) mod p;
36                          dec(i);
37                     end;
38               cc:=(z*ksm(z2,p-2)) mod p;
39          end;
40 begin
41      readln(n,m);
42      i:=cc(n+m,n);j:=i;
43      i:=(i*m) mod p;
44      i:=(i*ksm(n+1,p-2)) mod p;
45      writeln((j-i+p) mod p);
46 end.                    

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏听Allen瞎扯淡

由 Java 到 Scala:如何优雅的跳出循环

在开发过程中,我们经常会遇到这样的需求:循环执行某个操作,当满足一定条件的时候循环终止。最常见的场景就是累加数组中的元素,一直到大于某个值,用伪代码来描述就是:

51410
来自专栏小樱的经验随笔

POJ 3278 Catch That Cow(BFS,板子题)

Catch That Cow Time Limit: 2000MS Memory Limit: 65536K Total Submissions...

31350
来自专栏菩提树下的杨过

再谈Silverlight中的对象序列化/反序列化

曾经发过一篇如何在Silveright中利用XmlSerializer序列化对象的文章“Silverlight中的序列化”,限于当时的认识有限,一度以为silv...

22180
来自专栏菩提树下的杨过

Flash/Flex学习笔记(8):ActionScript3.0中的面对对象

首先要习惯AS3.0的几个BT约定: 1.一个.as文件中,只能定义一个类 2.类名称必须与.as的文件名相同 3.类定义中必须要有package包声明 4.一...

18590
来自专栏抠抠空间

python常见模块之collections模块

一、模块简介 在内置数据类型(dict、list、set、tuple)的基础上,collections模块还提供了几个额外的数据类型:Counter、deque...

33960
来自专栏数据结构与算法

BZOJ3295: [Cqoi2011]动态逆序对(cdq分治)

对于序列A,它的逆序对数定义为满足i<j,且Ai>Aj的数对(i,j)的个数。给1到n的一个排列,按照某种顺序依次删

9230
来自专栏冷冷

【jfinal】扩展JFIANL 支持加载jar包中SQL模板

扩展 ActiveRecordPlugin 支持加载jar包中SQL模板 jfinal3.1 中新增了IStringSource ,这个接口方便大家扩展SQL...

216100
来自专栏java初学

java异常处理及自定义异常的使用

15270
来自专栏全沾开发(huā)

JavaScript异步编程:Generator与Async

20240
来自专栏杂烩

使用javascript让项目支持热插拔 原

    突然想起之前做过的一个小项目,项目虽小,需求却不小,要求解析特定格式的字符串,并且特定格式并非一成不变,想要一套系统能够支持解析多变的规则且更改规则时不...

18820

扫码关注云+社区

领取腾讯云代金券