题目地址：洛谷：【P1641】[SCOI2010]生成字符串 – 洛谷、BZOJ：Problem 1856. — [Scoi2010]字符串

题目描述

lxhgww最近接到了一个生成字符串的任务，任务需要他把n个1和m个0组成字符串，但是任务还要求在组成的字符串中，在任意的前k个字符中，1的个数不能少于0的个数。现在lxhgww想要知道满足要求的字符串共有多少个，聪明的程序员们，你们能帮助他吗？

输入输出格式

输入格式：
输入数据是一行，包括2个数字n和m

输出格式：
输出数据是一行，包括1个数字，表示满足要求的字符串数目，这个数可能会很大，只需输出这个数除以20100403的余数

输入输出样例

输入样例#1：

2 2

输出样例#1：

2

说明

对于30%的数据，保证1<=m<=n<=1000
对于100%的数据，保证1<=m<=n<=1000000

题解

30%的做法，设计状态dp[i][j]表示填到第i位，前面有j个0，转移枚举最后一位填啥。复杂度O(n^2)。
100%的做法，就比较玄学了。
我们考虑上面的状态，把它改成dp[i][j]表示填到第i位，1的个数与0的个数之差为j的状态，转移是这样的
[eq]\displaystyle dp[i][j] = dp[i-1][j+1]+dp[i-1][j-1][/eq]
把状态的转移在二维平面中表示出来，发现末尾选1就表示向右上方走，选0表示向右下方走。起点是(0, 0)，终点是(n+m, n-m)，求这样的路径数，相当于从n+m步里选择m步向右下走，即[eq]\mathrm{C}_{n+m}^m[/eq]。不合法的方案在这里则接触/越过了y=-1这条线。由对称性，我们知道(0, -2)到终点的路径翻折一下就是(0, 0)到终点且经过y=-1的路径，因此不合法的路径就是(0, -2)到终点的路径数，相当于从n+m步里选择m-1步向右下走，即[eq]\mathrm{C}_{n+m}^{m-1}[/eq]。答案为[eq]\mathrm{C}_{n+m}^m-\mathrm{C}_{n+m}^{m-1}[/eq]。随便算一下阶乘搞一下逆元就可以了，模数是质数所以可以用费马小定理。复杂度O(n)。

代码

// Code by KSkun, 2018/4
#include <cstdio>
#include <cstring>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline LL readint() {
    register LL res = 0, neg = 1;
    register char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MO = 20100403;

LL n, m, ans;

inline LL fpow(LL n, LL k) {
    LL res = 1;
    while(k) {
        if(k & 1) res = res * n % MO;
        n = n * n % MO;
        k >>= 1;
    }
    return res;
}

int main() {
    n = readint(); m = readint(); n += m;
    LL nr = 1, mr = 1, nmr = 1;
    for(LL i = 1; i <= n; i++) {
        if(i <= m) mr = mr * i % MO;
        if(i <= n - m) nmr = nmr * i % MO;
        nr = nr * i % MO;
    }
    ans = nr * fpow(mr, MO - 2) % MO * fpow(nmr, MO - 2) % MO;
    m--;
    nr = 1; mr = 1; nmr = 1;
    for(LL i = 1; i <= n; i++) {
        if(i <= m) mr = mr * i % MO;
        if(i <= n - m) nmr = nmr * i % MO;
        nr = nr * i % MO;
    }
    ans -= nr * fpow(mr, MO - 2) % MO * fpow(nmr, MO - 2) % MO;
    ans = (ans % MO + MO) % MO;
    printf("%lld", ans);
    return 0;
}