Description:

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

Hint:

\(n,m \le 10^6\)

Solution:

很妙的一道題

網(wǎng)格圖上的組合數(shù)學(xué)

直接做發(fā)現(xiàn)不可做,考慮轉(zhuǎn)化,借的圖:

我們把初始狀態(tài)設(shè)為原點(diǎn),最終狀態(tài)設(shè)為\((n+m,n-m)\)

選1代表向右上走,走選0代表向左上走

答案就是走到終點(diǎn),且不經(jīng)過\(y=-1\)這條直線的方案數(shù)(想一想,為什么?)

這不好求,轉(zhuǎn)化求總方案減去不合法方案,求經(jīng)過\(y=-1\)這條直線的方案數(shù)

然后不難發(fā)現(xiàn),路徑經(jīng)過\(y=-1\)的方案就等于從\((0,-2)\)出發(fā)的方案

列個(gè)方程就知道要向下走m-1步,即方案為\(C(n+m,m-1)\)

所以答案就是\(C(n+m,m)-C(n+m,m-1)\)

#include <map> #include <set> #include <stack> #include <cmath> #include <queue> #include <cstdio> #include <cstring> #include <cstdlib> #include <iostream> #include <algorithm> #define ls p<<1 #define rs p<<1|1 using namespace std; typedef long long ll; const int mxn=2e6+5,mod=20100403; int n,m,fac[mxn],ifac[mxn]; inline int read() {char c=getchar(); int x=0,f=1;while(c>'9'||c<'0') {if(c=='-') f=-1;c=getchar();}while(c<='9'&&c>='0') {x=(x<<3)+(x<<1)+(c&15);c=getchar();}return x*f; } inline int chkmax(int &x,int y) {if(x<y) x=y;} inline int chkmin(int &x,int y) {if(x>y) x=y;}int qpow(int a,int b) {int res=1,bs=a;while(b) {if(b&1) res=1ll*res*bs%mod;bs=1ll*bs*bs%mod;b>>=1;}return res; }inline ll C(int n,int m) {return 1ll*fac[n]*ifac[m]%mod*ifac[n-m]%mod; }int main() {cin>>n>>m;fac[0]=ifac[0]=1; for(int i=1;i<=n+m;++i) fac[i]=1ll*fac[i-1]*i%mod;ifac[n+m]=qpow(fac[n+m],mod-2);for(int i=n+m-1;i>=1;--i) ifac[i]=1ll*ifac[i+1]*(i+1)%mod;printf("%lld",(C(n+m,m)-C(n+m,m-1)+mod)%mod);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/list1/p/10540834.html

總結(jié)

以上是生活随笔為你收集整理的[SCOI2010]生成字符串的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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