[SCOI2010]生成字符串

Description

Luogu1641

BZOJ1856

Solution

我们把加入(1)视为向右上方走，加入(0)视为向右下方走。那么，全部方案数就是从((0,0))走到((n+m, n-m))的方案数，为({n+mchoose m})。然后，非法的方案数就是走到(y=-1)这条线上的方案数，根据对称性可以发现，从((0,0))走到(y=-1)上的一点等价于从((0,-2))走到那个点。所以要减去从((0,-2))走到((n+m, n-m))的方案数，为({n+mchoose m-1})。

Code

#include <cstdio>
#include <cstring>

typedef long long ll;
const int N = 100010;
const int M = 200010;
const ll mod = 20100403;

ll fac(ll x) {
  for (int i = x - 1; i; --i) x = x * i % mod;
  return x;
}

ll pow_mod(ll x, ll p) {
  ll ans = 1;
  for (; p; p >>= 1, x = x * x % mod)
    if (p & 1) ans = ans * x % mod;
  return ans;
}

ll inv(ll x) { return pow_mod(fac(x), mod - 2); }

ll C(ll x, ll y) { return fac(x) * inv(y) % mod * inv(x - y) % mod; }

int main() {
  ll n, m;
  scanf("%lld%lld", &n, &m);
  printf("%lld
", (C(n + m, m) - C(n + m, m - 1) + mod) % mod);
  return 0;
}