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

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