Description
有$N$ 个 $1$ 和 $M$ 个 $0$ 组成的字符串， 满足前 $k$ 个字符中 $1$ 的个数不少于 $0$ 的个数。
求这样字符串的个数。
$1<=M <=N<=1e6$
Solution
正难则反， 很难直接求出满足条件的字符串的个数， 就从反面考虑。
$N$个$1$ 和 $M$ 个 $0$ 组成的字符串总共有 $C(N + M, N)$ 个， 再减去不满足条件的 字符串的个数就能够得到答案了。
不满足条件的字符串个数为$C(N+M,N+1)$
证明与 卡特兰数的证明类似：
设一个 不满足条件的字符串 $0$ 的个数 比 $1$ 多 的 位置为 $k$。
并且 对于任意 $j <k$， 前$j$个字符中$num_1>=num_0$， 而前$k$个字符$num_1<num_0$。
很显然 $num_0=num_1+1$， 我们将这个 $k$ 个字符都取反， $0$ 变成 $1$， $1$ 变成 $0$。
$0$ 的个数减少 $1$ 个， $1$ 的个数 增加 $1$个，
那么取反后的字符串 中 $1$ 的个数为 $N+1$， $0$ 的个数为 $M-1$。
由于 $N+1$个$1$ ，$M-1$个$0$ 组成的字符串恰好有$C(N+M,N+1)$个。
所以我们接下来要证明 它们是 一 一对应的，（即$(N,M)$中不满足条件的字符串通过转换能 对应上 $(N+1, M-1)$ 每种字符串）
现在已知 $(N,M)$ 能通过转换变成 $(N+1,M-1)$ 且没有重复。
只需证明$(N+1,M-1)$ 通过转换 变成 $(N,M)$ ： 找到第一个 $1$ 比 $0$ 多的位置 $k$ 并把前 $k$ 个字符取反 即可。
证毕
最后答案就是 $C(N+M,N)-C(N+M,N+1)$。
Code
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std; const int mod = ;
const int N = 2e6 + ; ll fpow(ll a, ll b) {
ll re = ;
for (; b; b >>= , a = a * a % mod)
if (b & ) re = re * a % mod;
return re;
} ll fac[N], ans; int main()
{
int n, m, M;
scanf("%d%d", &n, &m);
M = n + m;
fac[] = fac[] = ;
for (int i = ; i <= M; ++i)
fac[i] = fac[i - ] * i % mod;
ans = fac[M] * fpow(fac[n], mod - ) % mod;
ans = ans * fpow(fac[m], mod - ) % mod;
ll tmp = fac[M] * fpow(fac[n + ], mod - ) % mod;
tmp = tmp * fpow(fac[m - ], mod - ) % mod;
ans = ans - tmp;
ans = (ans % mod + mod) % mod;
printf("%lld\n", ans);
}