[SCOI2010]生成字符串 题解（卡特兰数的扩展）

时间：2024-05-31 14:03:20

[SCOI2010]生成字符串

Description

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

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

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

Solution

1.本题可看为使组成01串中任意前缀中1的个数比0多，而0和1的个数不等；

2.我们可以将0看做向上走，1看做向右走，求从原点走到(n,m)不越过y=x的不同方案数；

3.那么我们考虑卡特兰数通项公式的来源，本题解可化为总方案数-不可行方案数，不合法方案数即为触碰到y=x+1的方案数，即C(n+m,m)-C(n+m,m-1)= (n+m)!/(n+1)!m!(n-

m+1)%20100403;

4.用扩展欧几里得求模mod=20100403剩余系下分母的逆元，计算对应的ans即可；

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

using namespace std;

const long long mod=20100403;

long long n,m,i,ans,j,k,q;

void exgcd(long long a,long long b,long long &gcd,long long &x,long long &y) //Çó³Ë·¨ÄæÔª

{

    if(!b){

		x=1;

		y=0;

		gcd=a;

		return;

	}

    exgcd(b,a%b,gcd,y,x);

	y-=x*(a/b);

	return;

}

long long cul(long long a,long long b)

{

    long long gcd,x,y;

	exgcd(a,b,gcd,x,y);

    if(gcd==1)return(x+b)%b;

}

int main()

{

    scanf("%d%d",&n,&m);

	j=n-m+1;

	k=n+1;

    for(i=n+1;i<=n+m;i++)j=(j%mod)*(i%mod)%mod;

    for(i=2;i<=m;i++)k=(k%mod)*(i%mod)%mod;

    q=cul(k,mod);

	ans=j*q%mod;

    printf("%d\n",ans);

	return 0;

}

卡特兰数基础知识部分可以参考我的题解：http://www.cnblogs.com/COLIN-LIGHTNING/p/8450053.html

相关文章