組み合わせ 動的計画法 拡張ユークリッド互除法 atcoder

ABC145 D - Knight

ABC145 D - Knight
Feb. 2, 2020, 1:52 p.m.

目次

問題

https://atcoder.jp/contests/abc145/tasks/abc145_d

整数$X$, $Y$が与えられる.
$(0, 0)$から出発し、$(+1, +2)$、または$(+2, +1)$の移動のみを繰り返し$(X, Y)$まで到着するのに何通りの道があるかを答える問題.
到着不可能の場合は0通り.

解説

$X$, $Y$の最大値が$10^6$なので、$O(n \log n)$以下の計算量ではければ間に合いません.
移動の仕方が2通りしかないので、深さ優先探索でマス目を移動していき到達するケースを数えていくという解が思いつきますが、計算量は$O(2^n)$で間に合いません.
そこで移動の制約に着目し、$(+1, +2)$、$(+2, +1)$の移動をする回数をそれぞれ$n$, $m$とおくと、以下の連立方程式が得られます.

  • (1) 移動するごとにxとy合わせて3ずつ増加するので、$X + Y$は3の倍数であるはずです.
  • (2) 移動回数なので0以上です.また、必ず1は移動するのでXの最大値$10^6$以下です。
  • (3) (4) 移動量を回数分だけ繰り返すと$(X, Y)$に到着するという意味です.

$$
\begin{cases}
X + Y \equiv 0 \pmod{3} - (1) \
0 \leq n, m \leq 10^6 - (2) \
n + 2m = X - (3) \
2n + m = Y - (4)
\end{cases}
$$

(3) (4) を$n$、$m$について変形して、

$$
\begin{cases}
m = (2X - Y)/3 - (5) \
n = (Y - m)/2 - (6)
\end{cases}
$$

ここまでで$(+1, +2)$の移動を$n$回、$(+2, +1)$を$m$回するということが求まりました.

次にゴールまでの道順を求めますが、これは$n$個の$(+1, +2)$と$m$個の$(+2, +1)$の並べ方の数だけあることになります.
全移動は$m + n$回で、その中で$n$個の位置を決めていくので$_{m+n}C_{n}$の組み合わせです.
あとは、これを$(n \log n)$以下の計算量で求めるだけです.

$_{n}C_{k}$は高校数学でも出てくるように以下の式で計算できます.

$$
_{n}C_{k} = \frac{n!}{k!(n - k)!}
$$

例えば、$_{5}C_{2}$なら、

$$
_{5}C_{2} = \frac{5!}{2!(5 - 2)!} = \frac{5 \cdot 4}{2 \cdot 1} = 10
$$

ここで$_{n}C_{k}$は3つのファクトリアルから計算出来ることが分かります.
これらはすべてまとめてボトムアップ動的計画法で$O(\log n)$で計算出来ます.

$10^9 + 7$で割った答えを求めるので、割り算のところだけそのままでは計算
できないので、割り算の代わりに逆元との積に置き換える必要があります.

$$
_{n}C_{k} = n! \times (k!(n - k)!)^{-1} \pmod{10^9+7}
$$

逆元は拡張ユークリッドというアルゴリズムで$O(\log n)$で求める事ができます.

計算量

$$
O(n + m)
$$

解答

 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
44
45
46
47
48
49
50
51
52
53
54
55
Int X_, Y_;
Int fac[MAX_M];

void input() {
  cin >> X_ >> Y_;
}

void buildFact() {
    fac[0] = fac[1] = 1;
    for (int i = 2; i < MAX_M; i++){
        fac[i] = fac[i - 1] * i % MOD;
    }
}

// Extended Euclid
Int modinv(Int a, Int p) {
  Int b = p, u = 1, v = 0;
  while (b) {
    Int t = a / b;
    a -= t * b; swap(a, b);
    u -= t * v; swap(u, v);
  }
  u %= p;
  if (u < 0) u += p;
  return u;
}

Int nCk(int n, int k){
    if (n < k) return 0;
    if (n < 0 || k < 0) return 0;
    return fac[n] * modinv((fac[k] * fac[n - k] % MOD), MOD) % MOD;
}

void solve() {
  buildFact();
  if ((X_ + Y_) % 3 != 0) {
    cout << 0 << endl;
    return;
  }

  Int m = (2 * X_ - Y_) / 3;
  Int n = (Y_ - m)/2;
  if (m < 0 || n < 0) {
    cout << 0 << endl;
    return;
  }

  cout << nCk(m + n, n) << endl;
}

int main(void) {
  input();
  solve();
  return 0;
}