[洛谷P1641]生成字符串lyh's blog

难度：省选/NOI-

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

Sample input

2 2

Sample output

2

说明

        每点2秒
        对于30%的数据，保证1≤m≤n≤1000
        对于100%的数据，保证1≤m≤n≤1000000
        来源：SCACM 2010

题解

        更让人头秃的计数题（前一个是这个）…
        将字符序号（从1开始）看做横坐标x，前x个字符中1的数目与0的数目之差为纵坐标y，那么字符的选取可以看做坐标系上从点(0，0)开始的一条条连续的折线，它的终点为(n+m，n-m)。
        根据这个思路，从点(0，0)开始，选1就向右上方走，选0向右下方走，直到点(n+m，n-m)。这样的总的连线便对应一个字符串，容易知道若折线终点为(n+m，n-m)，那么整个过程1的数量一定为n，0的数量一定为m，不可能超出这个限制。显然在这种情况下方案数为$C^m_{n+m}$（从n+m步中选m步向下走）。
        如何限制前k个字符中1的数量不小于0的数量呢？如果1的数量小于0的数量，则纵坐标应小于0，连线一定与y=-1有所交集。下面证明与y=-1有交集的方案数与从(0，-2)开始到(n+m，n-m)方案数相同。
        对于一个从(0，0)开始且与y=-1有交集的连线（称之为非法连线），取其与y=-1的第一个交点p，将[0，p]的部分折到y=-1的下方。这样得到的连线显然是唯一的并且起点成为(0，-2)，这还是一个从(0，-2)开始结束于(n+m，n-m)的连线。同样对于一个从(0，-2)开始结束于(n+m，n-m)的连线，它与y=-1必然有交集，取其第一个交点p，将[0，p]的部分折到上方，得到一条从(0，0)开始的非法连线。从上面的讨论可以看出，非法连线与从(0，-2)开始在(n+m，n-m)结束的连线有着一一对应关系，它们的方案数必然是相同的，证毕。
        那从(0，-2)到(n+m，n-m)有多少方案呢？由于每一次都一定向右走，但是不一定向上还是向下，不妨假设向上走了x步，则向下走了m+n-x步，由于最后停在了(n+m，n-m)上，故有：

$x-(m+n-x)=n-m+2$

解得x=n+1，所以方案数为$C_{n+m}^{n+1}$，这个数也等于$C_{n+m}^{m-1}$。于是题目实质上是求$C_{m+n}^m-C_{m+n}^{m-1}$对20100403的模。
首先想到的是杨辉三角递推法，但那样一定会超时。注意到组合数的阶乘公式为：

$C_n^m=\frac {n!} {m!(n-m)!}$

分子分母的模很易求，但除法的模并不那样易求，这里需要乘法逆元来求除法的模（20100403是一个大质数）。
只需预处理出阶乘，再用费马小定理或者扩展欧几里得算法求出逆元，利用逆元求出除法的模，问题便得以解决。

//费马小定理求逆元
#include<iostream>

#define MOD 20100403
using namespace std;
long long op[2000001], n, m;

inline long long find(long long x) {//快速幂
    int p = MOD - 2;
    long long ans = 1;
    while (p > 0) {
        if ((p & 1) > 0)ans *= x, ans %= MOD;
        x *= x;
        x %= MOD;
        p >>= 1;
    }
    return ans;
}

int main() {
    cin >> n >> m;
    op[0] = 1;
    for (int i = 1; i <= n + m; i++)op[i] = op[i - 1] * i % MOD;
    long long a = find(op[m] * op[n] % MOD), b = find(op[m - 1] * op[n + 1] % MOD);//a和b是逆元
    long long c = op[n + m] * a % MOD, d = op[n + m] * b % MOD;
    long long ans = c - d;
    if (ans < 0)ans += MOD;
    cout << ans;
    return 0;
}

//扩展欧几里得算法求逆元
#include<iostream>

#define MOD 20100403
using namespace std;
long long op[2000001], n, m;

int exGcd(int a, int b, long long &x, long long &y) {//扩展欧几里得算法
    if (b == 0) {
        x = 1, y = 0;
        return a;
    }
    int t = exGcd(b, a % b, y, x);
    y -= a / b * x;
    return t;
}

inline long long find(int p) {
    long long x, y;
    exGcd(MOD, p, x, y);
    while (y < 0)y += MOD;
    return y % MOD;
}

int main() {
    cin >> n >> m;
    op[0] = 1;
    for (int i = 1; i <= n + m; i++)op[i] = op[i - 1] * i % MOD;
    long long a = find(op[m] * op[n] % MOD), b = find(op[m - 1] * op[n + 1] % MOD);
    long long c = op[n + m] * a % MOD, d = op[n + m] * b % MOD;
    long long ans = c - d;
    if (ans < 0)ans += MOD;
    cout << ans;
    return 0;
}