这题首先就得有一个画坐标系的想法，这很智障，我一开始也没有想出来。
我们设$X = Num[1] + Num[0]$, $Y = Num[1] - Num[0]$
也就是将1的个数加上0的个数设为X横坐标，把其和设为纵坐标。
稍微画一下图，如果我们从原点开始向右上方走(y = x)，那么就是$X + 1, Y + 1$，表示我们选择了1,，如果朝右下角走$y = - x$那么就是$X + 1, Y - 1$，表示我们选择了0。
很显然最后的方案数就是从原点走到$(N + M),(N - M)$节点。
因为无论如何$X$都是加一，所以步数一定是$N + M$步，而我们要选出$M$次向下走，方案数就是$C^{N +M} _M$。
当然，这是没有考虑限制情况。题目要求$1$的个数不能超过$0$的个数。发现也就是不能超过$y = - 1$这条直线。而经过直线的方案数就是$C^{N +M} _{M - 1}$
然后最后的答案就是
这种东西直接预处理前缀积然后逆元一下就好了…1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
using namespace std ;
typedef long long LL ;
const LL MAXN = 1000010 << 1 ;
const LL MAXM = 1000010 << 1 ;
const LL Inf = 0x7fffffff ;
const LL Mod = 20100403 ;
LL N, M, Fac[MAXN], Inv[MAXN] ;
inline LL Read() {
LL X = 0, F = 1 ; char ch = getchar() ;
while (ch > '9' || ch < '0') F = (ch == '-' ? - 1 : 1), ch = getchar() ;
while (ch >= '0' && ch <= '9') X=(X<<1)+(X<<3)+(ch^48), ch = getchar() ;
return X * F ;
}
inline LL QUCIK_POW(LL X, LL Y) {
LL Ans = 1 ; while (Y) {
if (Y & 1) Ans = Ans * X % Mod ;
X = X * X % Mod ; Y >>= 1 ;
} return Ans ;
}
inline LL C(LL X, LL Y) {
LL U = Fac[X] * Inv[Y] % Mod ;
return U * Inv[X - Y] % Mod ;
}
int main() {
N = Read() ; M = Read() ; Fac[0] = 1 ;
for (LL i = 1 ; i <= N + M ; i ++)
Fac[i] = Fac[i - 1] * i % Mod ;
Inv[N + M] = QUCIK_POW(Fac[N + M], Mod - 2) ;
for (LL i = N + M - 1 ; i >= 0 ; i --)
Inv[i] = Inv[i + 1] * (i + 1) % Mod ;
printf("%lld", (C(N + M, M) - C(N + M, M - 1) + Mod) % Mod) ;
return 0 ;
}