题解 P1641 【[SCOI2010]生成字符串】

xyz32768 · 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;
}