BZOJ1856[Scoi2010]字符串——组合数学+容斥

题目描述

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

输入

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

输出

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

样例输入

2 2

样例输出

提示

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

将选$1$看成往右走，选$0$看成往上走，那么要求的就是从$n*m$的网格的左下角走到右上角且不能穿过$y=x$的方案数。

将不能穿过$y=x$看成不能走到$y=x+1$，答案就是总方案数(即没有不能穿过$y=x$限制的方案数)-走到$y=x+1$的方案数。

将起点关于$y=x+1$对称到$(-1,1)$，那么走到$y=x+1$的方案数就是从$(-1,1)$走到$(n,m)$只能往右和往上走的方案数。

最终答案就是$C_{n+m}^{n}-C_{n+m}^{n+1}$，注意当$n<m$时答案为$0$。

#include<set>

#include<map>

#include<queue>

#include<stack>

#include<cmath>

#include<vector>

#include<bitset>

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int mod=20100403;

int n,m;

int fac[2000010];

int inv[2000010];

int C(int n,int m)

{

	return 1ll*fac[n]*inv[m]%mod*inv[n-m]%mod;

}

int main()

{

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

	inv[0]=inv[1]=fac[0]=fac[1]=1;

	for(int i=2;i<=n+m;i++)

	{

		fac[i]=1ll*fac[i-1]*i%mod;

		inv[i]=1ll*(mod-mod/i)*inv[mod%i]%mod;

	}

	for(int i=2;i<=n+m;i++)

	{

		inv[i]=1ll*inv[i-1]*inv[i]%mod;

	}

	if(n>=m)

	{

		printf("%d",(C(n+m,n)-C(n+m,n+1)+mod)%mod);

	}

	else

	{

		printf("0");

	}

}

巴特西

BZOJ1856[Scoi2010]字符串——组合数学+容斥

题目描述

输入

输出

样例输入

样例输出

提示

最新文章

热门文章