[SCOI2010] 生成字符串

题意

• 给定 $n$, $m$ ；
• 生成 $n$ 个 $1$ ，$m$ 个 $0$ 组成的字符串；
• 满足在任意一个前缀中，$1$ 的个数大于等于 $0$ 的个数。

题解

将选择 $1$ 看作向右走， $0$ 看作向上走，那么所求即为从 $(0, 0)$ 出发，到 $(n, m)$ ，不经过直线 $x - y + 1 = 0$ 的方案数。

先不考虑个数限制，所有的方案数为 $\binom {n + m} n$ 。

接下来考虑不合法的方案数

如图，所有经过 $x - y + 1 = 0$ 直线的路径，可以在第一次经过直线处翻折，使得终点为 $(m - 1, n + 1)$ 。

同时对于到 $(m - 1, n + 1)$ 的所有路径，沿第一次经过直线处翻折，得到唯一一条非法路径。

因而非法的个数为 $\binom {n + m} {n + 1}$ 。

答案为 $\binom {n + m} n - \binom {n + m} {n + 1}$ 。

代码

提交记录

/*
author: byronwan
problem:
    url: https://www.luogu.com.cn/problem/P1641
    title: [SCOI 2010] 生成字符串
*/

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll MOD = 20100403, MAXN = 2e6 + 10;

ll n, m;

ll qpow(ll x, ll p)
{
    return !p ? 1 : p & 1 ? x * qpow(x, p ^ 1) % MOD : qpow(x * x % MOD, p >> 1);
}

ll fac[MAXN], inv[MAXN];
void init()
{
    fac[0] = 1;
    for (ll i = 1; i < MAXN; i++) fac[i] = fac[i - 1] * i % MOD;
    inv[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2);
    for (ll i = MAXN - 2; i >= 0; i--) inv[i] = inv[i + 1] * (i + 1) % MOD;
}

ll comb(ll n, ll m) { return fac[n] * inv[m] % MOD * inv[n - m] % MOD; }

int main()
{
    cin >> n >> m;
    init();
    cout << (comb(n + m, n) - comb(n + m, n + 1) + MOD) % MOD << endl;
}