P1641 [SCOI2010]生成字符串

将字符串可视化，记当前 $1$ 的个数为 $i$ ，$0$ 的个数为 $j$ ，横坐标表示 $i + j$ ，纵坐标表示 $i - j$ ，则当该图像经过了 $y = -1$ 时不合法。总共的字符串个数为 $n + m$ 个位置中选择 $n$ 个位置为 $1$ ，即 $\binom{n + m} n$ ，现在考虑如何计算不合法的情况，即一定经过了 $y = -1$ 的情况。

如图是一种不合法的情况。

现在需要构造一种情况的答案和原问题的答案相同。对于每一个不合法的答案，一定经过了 $y = -1$ ，我们将第一次与 $y = -1$ 的点之前的线段沿 $y = -1$ 翻折，显然，从起点到该点的方案数一定是一样的。在原问题中一定有 $n \ge m$ ，所以终点一定在 $y = -1$ 上方，而翻转后的起点是 $(0, -2)$ ，所以一定经过了直线 $y = -1$ ，而答案不变。

再整体向上平移 $2$ 个单位，终点成为 $(n +m, n - m +2)$ ，同理方案数为 $\binom{n + m}{m - 1}$ ，所以最终答案为 $\binom{n + m} n - \binom{n + m}{m - 1}$ 。

查看代码

#include <iostream>
#include <cstdio>
typedef long long LL;
using namespace std;
const int N = 2e6 + 10, mod = 20100403;
int fact[N], infact[N];
int qp(int a, int k)
{
    int res = 1 % mod;
    while (k)
    {
        if (k & 1)
            res = (LL)res * a % mod;
        a = (LL)a * a % mod;
        k >>= 1;
    }
    return res;
}
int C(int a, int b)
{
    return (LL)fact[a] * infact[b] % mod * infact[a - b] % mod;
}
int main()
{
    int n, m;
    cin >> n >> m;
    fact[0] = infact[0] = 1;
    for (int i = 1; i <= n + m; i++)
    {
        fact[i] = (LL)fact[i - 1] * i % mod;
        infact[i] = (LL)infact[i - 1] * qp(i, mod - 2) % mod;
    }
    cout << ((C(n + m, n) - C(n + m, m - 1)) % mod + mod) % mod;
    return 0;
}