南阳做网站优化价格/seo小白入门教学

前言

传送门 :

E. White and Black Balls

$tag:$基础课原题 组合记数 画图分析 卡特兰数
题意 :
给定$n$个白球,$m$个黑球,询问有多少种合法放置

条件 ：
对于所有的$i$满足$cn{t}_{wi}<=cn{t}_{b_i}+K$

思路 :
显然这题是 AcWing 889. 满足条件的01序列 基础课的变式

但是分析方式不变,图(不是我的,没带笔

因此从$(0,0)->(n,m)的路径数$ 也就是从$(0,0)->(n+k+1,m-k-1)$的路径数

即答案就是$C_{n+m}^n-C_{n+m}^{m-k-1}$

Code

int fact[N],infact[N];int qmi(int a,int b){int res = 1;while(b){if(b&1) res = (ll)res*a%mod;a = (ll) a*a%mod;b>>=1;}return res;
}void init() {fact[0] = infact[0] = 1;for (int i = 1; i < N; i++) {fact[i] = (ll)fact[i - 1] * i % mod;infact[i] = (ll)infact[i - 1] * qmi(i, mod - 2) % mod;}
}void solve()
{init();int n,m,k;cin>>n>>m>>k;if(n > k + m){cout<<0<<endl;return ;}ll a = 0, b = 0;a = (ll)fact[n + m] * infact[n] % mod * infact[m] % mod;b = (ll)fact[n + m] * infact[n - k - 1] % mod * infact[m + k + 1] % mod;cout<<(a-b+mod)%mod<<endl;}