題目描述

lxhgww最近接到了一個(gè)生成字符串的任務(wù)，任務(wù)需要他把n個(gè)1和m個(gè)0組成字符串，但是任務(wù)還要求在組成的字符串中，在任意的前k個(gè)字符中，1的個(gè)數(shù)不能少于0的個(gè)數(shù)?，F(xiàn)在lxhgww想要知道滿足要求的字符串共有多少個(gè)，聰明的程序員們，你們能幫助他嗎？

輸入

輸入數(shù)據(jù)是一行，包括2個(gè)數(shù)字n和m

輸出

輸出數(shù)據(jù)是一行，包括1個(gè)數(shù)字，表示滿足要求的字符串?dāng)?shù)目，這個(gè)數(shù)可能會(huì)很大，只需輸出這個(gè)數(shù)除以20100403的余數(shù)

樣例輸入

2 2

樣例輸出

2

提示

【數(shù)據(jù)范圍】
對(duì)于30%的數(shù)據(jù)，保證1<=m<=n<=1000
對(duì)于100%的數(shù)據(jù)，保證1<=m<=n<=1000000

?

將選$1$看成往右走，選$0$看成往上走，那么要求的就是從$n*m$的網(wǎng)格的左下角走到右上角且不能穿過$y=x$的方案數(shù)。

將不能穿過$y=x$看成不能走到$y=x+1$，答案就是總方案數(shù)(即沒有不能穿過$y=x$限制的方案數(shù))-走到$y=x+1$的方案數(shù)。

將起點(diǎn)關(guān)于$y=x+1$對(duì)稱到$(-1,1)$，那么走到$y=x+1$的方案數(shù)就是從$(-1,1)$走到$(n,m)$只能往右和往上走的方案數(shù)。

最終答案就是$C_{n+m}^{n}-C_{n+m}^{n+1}$，注意當(dāng)$n<m$時(shí)答案為$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");} }

轉(zhuǎn)載于:https://www.cnblogs.com/Khada-Jhin/p/10954692.html

總結(jié)

以上是生活随笔為你收集整理的BZOJ1856[Scoi2010]字符串——组合数学+容斥的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。