Bzoj 1856: [Scoi2010]字符串卡特兰数,乘法逆元,组合数,数论

1856: [Scoi2010]字符串

Time Limit: 5 Sec Memory Limit: 64 MB
Submit: 1194 Solved: 651
[Submit][Status][Discuss]

Description

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

Input

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

Output

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

Sample Input

2 2

Sample Output

HINT

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

Source

Day2

题解：

在任意的前k个字符中，1的个数不能少于0的个数？？？

好熟悉。。。卡特兰数。。。

当然你也可以在纸上推一下。

直接套公式：当n为1的个数，m为0的个数时，卡特兰数为C(n+m,n)-C(n+m,m-1)。

组合数C(n,r)直接用逆元计算即可。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define MOD 20100403
 4 #define LL long long
 5 LL ksm(LL bb,LL pp,LL kk)
 6 {
 7     LL s=1;
 8     while(pp>0)
 9     {
10         if(pp%2!=0)s=(s*bb)%kk;
11         pp/=2;
12         bb=(bb*bb)%kk;
13     }
14     return s;
15 }
16 LL C(LL n,LL m)
17 {
18     LL s1=1,s2=1,nn=n,i;
19     if(m>n-m)m=n-m;
20     for(i=1;i<=m;i++)
21     {
22         s1=(s1*nn)%MOD;nn--;
23         s2=(s2*i)%MOD;
24     }
25     return (s1*ksm(s2,MOD-2,MOD))%MOD;
26 }
27 int main()
28 {
29     LL n,m;
30     scanf("%lld %lld",&n,&m);
31     printf("%lld",((C(n+m,n)-C(n+m,m-1))%MOD+MOD)%MOD);
32     fclose(stdin);
33     fclose(stdout);
34     return 0;
35 }

Bzoj 1856: [Scoi2010]字符串 卡特兰数,乘法逆元,组合数,数论