自动搬运

查看原文

来自洛谷，原作者为

	xyz32768 “各方面相差太远”

搬运于2025-08-24 21:27:25，当前版本为作者最后更新于2017-08-27 20:43:00，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

可以考虑把$1$的个数与$0$的个数的和看成$x$坐标，$1$的个数与$0$的个数的差看成$y$坐标，那么如下图：

向右上走（$x$坐标加$1$，$y$坐标加$1$）就表示这个字符选择$1$。

向右下走（$x$坐标加$1$，$y$坐标减$1$）就表示这个字符选择$0$。

这样子，如果不考虑限制条件，就表示从$(0,0)$走$n+m$步到达$(n+m,n-m)$，这相当于从$n+m$步中选出$m$步向右下走，也就是$C(n+m,m)$。

考虑限制条件，任意前缀中$1$的个数不少于$0$的个数，也就是这条路径不能经过直线$y=-1$。可以通过对称性发现，从$(0,0)$走到直线$y=-1$上的一点，相当于从$(0,-2)$走到该点。也就是说，路径经过直线$y=-1$的方案数就是从$(0,-2)$走$n+m$步到达$(n+m,n-m)$，这个方案数可以用组合数表示为$C(n+m,m-1)$。

所以最后结果为$C(n+m,m)-C(n+m,m-1)$。对于组合数，可以预处理阶乘后用乘法逆元计算。

代码：

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
inline int read() {
    int res = 0; bool bo = 0; char c;
    while (((c = getchar()) < '0' || c > '9') && c != '-');
    if (c == '-') bo = 1; else res = c - 48;
    while ((c = getchar()) >= '0' && c <= '9')
        res = (res << 3) + (res << 1) + (c - 48);
    return bo ? ~res + 1 : res;
}
const int N = 2e6 + 5, PYZ = 20100403;
int n, m, fac[N], inv[N];
int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % PYZ;
        a = 1ll * a * a % PYZ;
        b >>= 1;
    }
    return res;
}
int C(int x, int y) {
    int z = 1ll * fac[x] * inv[y] % PYZ;
    return 1ll * z * inv[x - y] % PYZ;
}
int main() {
    int i; fac[0] = 1; n = read(); m = read();
    for (i = 1; i <= n + m; i++) fac[i] = 1ll * fac[i - 1] * i % PYZ;
    inv[n + m] = qpow(fac[n + m], PYZ - 2);
    for (i = n + m - 1; i >= 0; i--)
        inv[i] = 1ll * inv[i + 1] * (i + 1) % PYZ;
    printf("%d\n", (C(n + m, m) - C(n + m, m - 1) + PYZ) % PYZ);
    return 0;
}