2020-04-26

AtCoder ABC 145 D - Knight (緑色, 400 点)

AtCoder AtCoder400点 ABC-D 二項係数数え上げ問題二次元グリッドナイトの動き方程式連立一次方程式式変形緑色diff 経路数の数え上げ駒(コマ)や石やコインを扱う問題

この問題のおかげで、僕の二項係数記事が一躍広く普及することになったのだった。

問題へのリンク

問題概要

二次元グリッドの原点 $(0, 0)$ にチェスのナイトの駒がある。

ナイトの駒はマス $(i, j)$ にあるとき $(i+1, j+2)$ か $(i+2, j+1)$ のどちらかのマスにのみ動かすことができる。

ナイトの駒をマス $(X, Y)$ まで移動させる方法は何通りあるか、1000000007 で割った余りを求めよ。

制約

$1 \le X \le 10^{6}$
$1 \le Y \le 10^{6}$

考えたこと

ナイトといいつつ、後戻りはできない。つまり、原点 $(0, 0)$ からドンドン離れていく方向にしか動くことはできない。

よって、それほどヤバい数え上げにはならなさそうという予感がする。そもそも、この手の経路数数え上げ問題として

最短経路の数え上げは簡単 ( $(0, 0)$ から $(a, b)$ まで至る経路数は ${}_{a+b}{\rm C}_{a}$ 通りと、一発で求められる)
最短経路とは限らない経路の数え上げは難しい (お姉さん動画を参照)

という両極端な状況がある。今回の問題は、このうちの前者寄りだろうという気持ちになるわけだ。

方程式を立ててみる

ここで方程式を立ててみよう。

$(i, j)$ から $(i+1, j+2)$ へ行く移動が $n$ 回
$(i, j)$ から $(i+2, j+1)$ へ行く移動が $m$ 回

であるとすると、

X 軸方向の移動距離は、 $n + 2m$ と表せるので、 $n + 2m = X$
Y 軸方向の移動距離は、 $2n + m$ と表せるので、 $2n + m = Y$

という式を立てることができる。連立方程式が立ったので、これを $n, m$ について解いてみる。こういう対称性の綺麗な方程式を解くコツは最初に足してしまうこと。そうすると、

$3n + 3m = X+Y$

となる。よって

$n + m = \frac{X + Y}{3}$

となる。これを使うと、

$n = (2n + m) - (n + m) = Y - \frac{X+Y}{3} = \frac{-X + 2Y}{3}$
$m = (n + 2m) - (n + m) = X - \frac{X+Y}{3} = \frac{2X - Y}{3}$

と求めることができる。なんと、 $(2, 1)$ の動きと、 $(1, 2)$ の動きをそれぞれ何回行えばよいのかがただ一通りに決まってしまうのだ。

最短経路の数え上げと一緒

ここまで来ると、次の問題とまったく一緒と言える。

$(0, 0)$ から $(n, m)$ へ至る最短経路が何通りあるか求めよ

答えは、 ${}_{n+m}{\rm C}_{n}$ 通りとなる。ただし注意点として

$n, m$ がそもそも整数でない場合は 0 通り ( $X+Y$ が 3 の倍数かどうかを判定すれば OK)
$n \lt 0$ または $m \lt 0$ となる場合は 0 通り

となる。二項係数の求め方については以下の記事を参考に。

drken1215.hatenablog.com

#include <bits/stdc++.h>
using namespace std;

// modint: mod 計算を int を扱うように扱える構造体
template<int MOD> struct Fp {
    long long val;
    constexpr Fp(long long v = 0) noexcept : val(v % MOD) {
        if (val < 0) val += MOD;
    }
    constexpr int getmod() { return MOD; }
    constexpr Fp operator - () const noexcept {
        return val ? MOD - val : 0;
    }
    constexpr Fp operator + (const Fp& r) const noexcept { return Fp(*this) += r; }
    constexpr Fp operator - (const Fp& r) const noexcept { return Fp(*this) -= r; }
    constexpr Fp operator * (const Fp& r) const noexcept { return Fp(*this) *= r; }
    constexpr Fp operator / (const Fp& r) const noexcept { return Fp(*this) /= r; }
    constexpr Fp& operator += (const Fp& r) noexcept {
        val += r.val;
        if (val >= MOD) val -= MOD;
        return *this;
    }
    constexpr Fp& operator -= (const Fp& r) noexcept {
        val -= r.val;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr Fp& operator *= (const Fp& r) noexcept {
        val = val * r.val % MOD;
        return *this;
    }
    constexpr Fp& operator /= (const Fp& r) noexcept {
        long long a = r.val, b = MOD, u = 1, v = 0;
        while (b) {
            long long t = a / b;
            a -= t * b; swap(a, b);
            u -= t * v; swap(u, v);
        }
        val = val * u % MOD;
        if (val < 0) val += MOD;
        return *this;
    }
    constexpr bool operator == (const Fp& r) const noexcept {
        return this->val == r.val;
    }
    constexpr bool operator != (const Fp& r) const noexcept {
        return this->val != r.val;
    }
    friend constexpr ostream& operator << (ostream &os, const Fp<MOD>& x) noexcept {
        return os << x.val;
    }
    friend constexpr Fp<MOD> modpow(const Fp<MOD> &a, long long n) noexcept {
        if (n == 0) return 1;
        auto t = modpow(a, n / 2);
        t = t * t;
        if (n & 1) t = t * a;
        return t;
    }
};

// 二項係数ライブラリ
template<class T> struct BiCoef {
    vector<T> fact_, inv_, finv_;
    constexpr BiCoef() {}
    constexpr BiCoef(int n) noexcept : fact_(n, 1), inv_(n, 1), finv_(n, 1) {
        init(n);
    }
    constexpr void init(int n) noexcept {
        fact_.assign(n, 1), inv_.assign(n, 1), finv_.assign(n, 1);
        int MOD = fact_[0].getmod();
        for(int i = 2; i < n; i++){
            fact_[i] = fact_[i-1] * i;
            inv_[i] = -inv_[MOD%i] * (MOD/i);
            finv_[i] = finv_[i-1] * inv_[i];
        }
    }
    constexpr T com(int n, int k) const noexcept {
        if (n < k || n < 0 || k < 0) return 0;
        return fact_[n] * finv_[k] * finv_[n-k];
    }
    constexpr T fact(int n) const noexcept {
        if (n < 0) return 0;
        return fact_[n];
    }
    constexpr T inv(int n) const noexcept {
        if (n < 0) return 0;
        return inv_[n];
    }
    constexpr T finv(int n) const noexcept {
        if (n < 0) return 0;
        return finv_[n];
    }
};

const int MOD = 1000000007;
using mint = Fp<MOD>;

mint solve(long long X, long long Y) {
    BiCoef<mint> bc(1100000);
    if ((X + Y) % 3 != 0) return 0;
    long long n = (-X + Y*2) / 3;
    long long m = (X*2 - Y) / 3;
    return bc.com(n+m, n);
}

int main() {
    long long X, Y;
    cin >> X >> Y;
    cout << solve(X, Y) << endl;
}