Rockdu's Blog

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

2 2

2

说明

limitation

每点2秒

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

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

来源：SCOI 2010

一道卡特兰数的变式。类似的，受卡特兰数的启发，我们仍然把1看成出栈操作，0看成入栈操作。在不考虑合法性的情况下我们有C(n + m, n) 种方法。又类似的，我们对一个不合法的情况，考虑从前往后第一次取到1比0多1个的时候，我们把前面的1,0取反，这时我们会得到一个有n - 1个1、m + 1个0的序列，而且枚举取反后的序列一定和操作前的序列一一对应。那么不合法序列共有C(n + m, n - 1)种。这个时候我们就可以线性递推组合数做这道题了（PS：快速幂求逆元好写多了呀）。

#include<cstdio>
#include<algorithm>
#include<cmath>
#define LL long long
using namespace std;
int n, m;
LL ans[2];
const LL mod = 20100403;
LL fpow(LL a, LL b, LL p) {
    LL ans = 1;
    while(b) {
        if(b & 1) ans = (ans * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return ans % p;
}
void count(int a, int b) {
    for(register int i = 1; i < b; ++i) {
        ans[0] = ans[1];
        (ans[1] *= (fpow(i + 1, mod - 2, mod) * (a - i)) % mod) %= mod;
    }
}
int main() {
    scanf("%d%d", &n, &m);
    if(n < m) {
        putchar('0');
        return 0;
    }
    const int down = n + m;
    ans[0] = 1, ans[1] = down;
    count(down, m);
    LL res = ans[1] - ans[0] >= 0 ? ans[1] - ans[0] : ans[1] - ans[0] + mod;
    printf("%d", res);
    return 0;
}