AtCoder Beginner Contest 145：D - Knight

問題

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

解法

各移動で原点から x, y 座標合わせて 3 は増加するから，(X + Y) が 3 で割り切れないとき，答えは 0 通り．

そうでないとき，操作の回数 n は (X + Y) / 3 回であると分かる．n が偶数のとき，|X - Y| は偶数になり，n が奇数の時は奇数になる．このようにならない場合は答えは 0 通り．

2 種類の操作はそれぞれ (n - |X - Y|) / 2 回と (n + |X - Y|) / 2 回行われると分かるので，前者を用いて C(n, (n - |X - Y|) / 2) 通りが答えとなる．コンビネーション計算は逆元を使う必要がある．

解答

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