ABC145D - Knight - acchan’s blog

問題概要

２次元平面上の原点(0, 0)にチェスのナイトの駒が置かれている。

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

目的地$(X, Y)$まで移動させる総数を$10^{9}+7$で割ったあまりを求めよ。

問題のリンクはこちら

制約

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

考察

DPによる考察

まず初めにDPで解けないかを考えた。具体的には、

$$ dp[i][j]: (i, j)までの移動させる方法の総和 $$

というDPを定義した時、遷移は、

\begin{eqnarray} dp[i][j]=\left\{ \begin{array}{ll} dp[i-1][j-2] & (y=2x) \\ dp[i-2][j-1] & (y=\frac{1}{2}) \\ dp[i-1][j-2]+dp[i-2][j-1] & (上記以外) \\ \end{array} \right. \end{eqnarray}

となる。しかしながら、今回の制約では $O(N^{2})$のプログラムは不適切である。

この問題のポイントとなる気付き

この問題を特に当たって、次のポイントに気がつくと考察を進めやすい。

パスカルの三角形を形成すること(次の章を参照)
点は全て $y = -x + 3*k, k:0以上の整数$にのること
X+Yの和は常に3の倍数になり、連続する３の倍数を形成している。
パスカルの三角形は、$y=\frac{1}{2}x$, $y=2x$, $y=-x+3k, k:0以上の整数$で囲まれること。

パスカルの三角形と逆元による考察

個数のカウント方法

具体的に点をプロットしてナイトの動きを観察する。移動することのできる総和をプロットした点に書き加えていく。(例えば、 $(1, 2)$は、$(0, 0)$からのみ移動できるので$1$である。この操作を$3$段程度行うと、 パスカルの三角形 を形成していることに気がついた。

つまり、$(X, Y)$が$n$段目の左から$r$番目にある時、 $_{n-1} C_{r-1} $ で計算できる

ことが言えるようになる。

(X, Y)がパスカルの三角形のどこに位置するか

あとは、点$(X, Y)$が$n$段目の左から$r$番目に該当するかを考える。

点 $(0, 0)$ を1段目とすると、

$(1, 2), (2, 1)$ → $1+2/3+1 = 2$ 段目 *$(2, 4), (3, 3), (4, 2)$ → $6/3+1 = 3$段目

のように (X+Y)/3+1が段数に相当する。

$n$段目だと判明したら、次は、その$n$段目の中で一番$y$座標が大きい点を探す。これは、$y = 2(n-1)$により求まるので、あとは、今求めた$y$を用いて、$r = y-Y+1$で求められる。

これらを求めることができたので、あとは、逆元を用いて、コンビネーションの計算をすることで答えとなる。

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;
typedef long long ll;
const int mod = 1e9+7;
const int NMAX=1000010;

ll fac[NMAX], finv[NMAX], inv[NMAX];

void init() {
  fac[0] = fac[1] = 1;
  finv[0] = finv[1] = 1;
  inv[1] = 1;
  for(int i = 2; i < NMAX; i++) {
    fac[i] = fac[i-1] * i % mod;
    inv[i] = mod - inv[mod%i] * (mod/i) % mod;
    finv[i] = finv[i-1] * inv[i] % mod;
  }
}

ll C(int n,int k) {
  if(n < k) return 0;
  if(n < 0 || k < 0) return 0;
  return fac[n] * (finv[k] * finv[n-k] % mod) % mod;
}

int main() {
  init();
  int X, Y; cin >> X >> Y;
  if((X+Y) % 3 != 0) {
    cout << 0 << endl;
    return 0;
  }
  int n = (X+Y) / 3+1;
  int k = 2*(n-1) - Y + 1; // y = 2xより最も上にくる点からどれだけ離れているか。
  cout << C(n-1, k-1) << endl;
  return 0;
}