[SCOI2010]生成字符串

发表于 | 更新于 | 阅读次数：

Description

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

Input Format

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

Output Format

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

Input Sample

1
2 2

Output Sample

1
2

Hint

每点2秒

对于30%的数据，保证$1 \le m \le n \le 1000$

对于100%的数据，保证$1 \le m \le n \le 1000000$

题解

灰常神奇的一道题（蒟蒻表示想不到。。。）

看了题解的构造之后感觉好像在哪里见过？？？

然后往下翻，大佬说这是小学奥数（看来这是我小学的锅了。。。）

然后我还看见了$Catalan$数。（看来是我初中的锅了。。。）

其实这道题目在构造出模型后问题就迎刃而解。（$dalao$们就别吐槽了）

先来看一下答案$C^{M}_{N+M}−C^{M−1}_{N+M}$。为什么答案是这个呢？

我们考虑建立一个坐标系，将$N+M$作为横坐标，$N−M$作为纵坐标。

横坐标表示的是字符串的长度，纵坐标表示的是$1$的个数和$0$的个数的差值。

然后对于在字符串后加入$1$，就相当于向右上方走一格。加入$0$则表示往右下方走一格。

那么题目的意思就是要求我们计算从$(0,0)$走到$(N+M,N−M)$，且不经过直线$y=−1$的所有方案数。

那么怎么统计方案呢？我们考虑先计算出所有情况再减去不合法情况。（正难则反？）

所有情况很显然是$C^{M}_{N+M}$，那不合法情况呢？

不合法情况是一定会穿过直线的$y=−1$的路径。

只要第一次穿过了直线$y=−1$就可以算作不合法方案，那么通过对称，我们将$(0,0)$对称到$(0,−2)$，此时从$(0,−2)$走到$(N+M,N−M)$的所有方案数就是所谓的不合法方案数。为什么呢？

由于$(N+M,N−M)$一定是在第一象限的，所以对于所有从$(0,−2)$走到$(N+M,N−M)$的路径，都一定会经过直线$y=−1$，就是说这里所有路径都是不合法的。

然后我们考虑路径中还未穿过直线$y=−1$的前面那一段。

我们可以通过对称将这段路径对称上去。这样就可以构造出一个从$(0,0)$开始走，经过直线$y=−1$后，再走到$(N+M,N−M)$的路径。

所以说，从$(0,−2)$走到$(N+M,N−M)$的所有方案数就是所谓的不合法方案数。

那么此时不合法方案总数就是$C^{M−1}_{N+M}$

此时问题转化为求$C^{M}_{N+M}−C^{M−1}_{N+M}$

但是题目要求求余，所以我们还需要结合逆元来计算。

这里就不多讲（下一篇会整理一下逆元）

放贷吗？放代码->

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <stdio.h>
#include <iostream>
#define Re register int
#define LL long long
#define MOD 20100403

int N,M,d,fac[2000005];

template <typename T> inline void read(T &var)
{
	T x=0; int w=0; char ch=0;
	while (!isdigit(ch)) w|=ch=='-',ch=getchar();
	while (isdigit(ch)) x=x*10+ch-'0',ch=getchar();
	var=w?-x:x;
}
void exgcd(LL a,LL b,LL &x,LL &y)
{
	if (!b) d=a,x=1,y=0;
	else exgcd(b,a%b,y,x),y-=x*(a/b);
}
inline LL inv(LL a,LL n)
{
	LL x,y; exgcd(a,n,x,y);
	return d==1?(x+n)%n:-1;
}
inline LL C(int x,int y)
{
	LL k=1LL*fac[x]*inv(fac[y],MOD)%MOD;
	return 1LL*k*inv(fac[x-y],MOD)%MOD;
}
int main(int argc, char const *argv[])
{
	read(N),read(M); fac[0]=1;
	for (Re i=1; i<=N+M; ++i)
		fac[i]=1LL*fac[i-1]*i%MOD;
	printf("%lld\n",(C(N+M,M)-C(N+M,M-1)+MOD)%MOD);
	return 0;
}