家を通り過ぎないランダムウォーク問題 [yukicoder No.660]

https://yukicoder.me/problems/no/660

前提知識

• カタラン数的数え方

解法

https://yukicoder.me/submissions/240696

全部で何回移動したかを全探索する。
これはN, N+2, N+4, ..., 2Nを全て計算する。
全部でn回移動するとする。
この時、合計で東にx回、西にy回移動すると定義すると、
y = (n - N)/2
x = n - y
だけ移動する必要がある。
これで組合せを計算するとcombination(x+y,x)であるが、これは最後以外に自宅に到達する経路も含まれる。
2次元座標で考えて(0,0)から(x,y)へ移動する事を考えると最後は東で終わる必要があるので(0,0)から(x-1,y)への経路を計算する。
(0,0)から(x-1,y)へ右か上かで移動する組合せを考えるが、y=x-Nを最後以外通らないようにする。
これはカタラン数の計算方法と同じやり方で計算ができる。
y=x-Nについて(x-1,y)を対称移動して、ダメな経路を計算する。
これを考えるとcombination(x+y, x) - combination(x+y, y-1)が答えになる。
これを全ての場合について足し合わせると答え。

int N;
Comb<mint, 401010> com;
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N;

    mint ans = 0;
    for (int n = N; n <= 2 * N; n += 2) {

        int y = (n - N) / 2;
        int x = n - y - 1;

        // y = x - Nで対称移動して引く
        mint d = com.aCb(x + y, x);
        d -= com.aCb(x + y, y - 1);

        ans += d;
    }
    cout << ans << endl;
}