Knight [AtCoder Beginner Contest 145 D]

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

前提知識

• 二項係数 mod 素数を高速に計算する方法

解説

https://atcoder.jp/contests/abc145/submissions/8484697

400点にしては問題が難しい感じがする。
何か全探索対象を探そう。

まず、(+1,+2)か(+2,+1)かの2通りの操作があるが、操作Aと操作Bとしておこう。
すると、AABと操作するのとABAと操作するのでは結果は変わらない。
しかも最終的な位置は操作Aをa回、操作Bをb回行うと、(a+2b, 2a+b)になる。
a+2b=X
2a+b=Y
を満たす必要があるので、操作回数は一意に定まる。
まずはこれを求める。
連立方程式を真面目に解いてもいいが、X,Yが10⁶までなので、aを全探索して探せばいい。
a,bで0以上の整数の解が見つからなければ0が答え。

あとは、Aがa個、Bがb個ある経路の組み合わせを求める。
これはちょうどC(a+b,a)となる。
mod10⁹+7で二項係数を高速に求める方法は知られているので、それを使うと答え。

int X, Y;
Comb<mint, 2010101> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> X >> Y;
    rep(a, 0, X + 1) {
        int b = X - a;
        if (b % 2 == 1) continue;

        b /= 2;
        if (2 * a + b == Y) {
            cout << com.aCb(a + b, a) << endl;
            return;
        }
    }
    cout << 0 << endl;
}