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

xyz32768

2017-08-27 20:43:00

Solution

可以考虑把$1$的个数与$0$的个数的**和**看成$x$坐标,$1$的个数与$0$的个数的**差**看成$y$坐标,那么如下图: ![这里写图片描述](http://img.blog.csdn.net/20170826103642649?watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQveHl6MzI3Njg=/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/SouthEast) 向右上走($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)$。对于组合数,可以预处理阶乘后用乘法逆元计算。 代码: ```cpp #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; } ```