くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU
トップ > AtCoder > Python3で解く AtCoder Beginner Contest 145 D - Knight

Python3で解く AtCoder Beginner Contest 145 D - Knight

AtCoder 競プロ ABC-D 二項係数 nCr 連立方程式

ナイトのコマがある動きをするときに、目的の場所にたどり着けるかどうかという問題。連立方程式も使うし、高速に{\displaystyle _nC_r}を計算する必要もある。結構内容としては盛りだくさんで難しい。久しぶりにモジュラ逆数について考えたので軽くまとめた。

概要

問題

  1. ナイトの駒が座標{\displaystyle (0, 0)}にいる。
  2. ナイトの駒は{\displaystyle (i,j)}にいるとき{\displaystyle (i+1,j+2)}　か{\displaystyle (i+2,j+1)}の２パターンの動きしかできない。
  3. ナイトの駒を{\displaystyle x, y}まで移動させたいが、何通りある？

解くときに考えた内容

連立方程式

  • {\displaystyle (i+1,j+2)}の行動回数を {\displaystyle m}、{\displaystyle (i+2,j+1)}の行動回数を {\displaystyle n}として考えると以下のように {\displaystyle m, n}を計算できる。

    {\displaystyle x = 2m + n}
    {\displaystyle y = m + 2n}
    {\displaystyle 2x-y = 3m}
    {\displaystyle 2y-x = 3n}
    {\displaystyle m = \frac{2x-y }{3}}
    {\displaystyle n = \frac{2y-x }{3}}

  • {\displaystyle m, n}さえ計算できれば{\displaystyle _{m+n}C_m}を計算すればいい（早く）

ここが今回の課題で、{\displaystyle mod\ p}における{\displaystyle _nC_r}を計算量少なく求めること。

nCrに関する前提
  • {\displaystyle _nC_r = \frac {n!}{r!(n-r)!}} = n! \times r^{-1}! \times (n-r)^{-1}!である
modに関する前提
  • {\displaystyle mod\ p}において、足し算・引き算・かけ算が成立する。( {\displaystyle a \% p}というのは {\displaystyle a}を{\displaystyle p}で割った余りのこと)
    • {\displaystyle a \% p + b \% p = (a + b) \% p} （例：{\displaystyle 12 \% 11 + 13 \% 11) = (12 + 13) \% 11) = 3})
    • {\displaystyle a \% p - b \% p = (a - b) \% p} （例：{\displaystyle 12 \% 11 - 13 \% 11) = (12 - 13) \% 11) = 10})
      (演算結果が負の場合は{\displaystyle p+}演算結果とすれば良い)
    • {\displaystyle a \% p \times b \% p = (a \times b) \% p} （例：{\displaystyle 12 \% 11 \times 13 \% 11) = (12 \times 13) \% 11) = 2})
  • 割り算について一般化できるのか これはモジュラ逆数というものである。直感的な話をすると、 {\displaystyle b \neq 0}において
    • {\displaystyle b}で割るということは{\displaystyle \frac{1}{b}} 掛けることであると同義であり、{\displaystyle \frac{1}{b} = b^{-1}}である。
    • {\displaystyle mod\ p}において、{\displaystyle \frac{1}{b}}とは何かというと、{\displaystyle b \times \frac{1}{b} = 1}が成立する値である。
    • 例えば {\displaystyle mod\ 11}において、{\displaystyle 4 \times \frac{1}{4} = 1}が成立するような{\displaystyle \frac{1}{4}}を考えると、{\displaystyle (1 + 11\times k) \div 4}が割り切れた時の値。例えば{\displaystyle k=1}とすると{\displaystyle 4 \times \frac{1}{4} = 12}なので{\displaystyle 4}で割り切れるので{\displaystyle \frac{1}{4}} \equiv 3 (余りは一緒ということで合同という時は{\displaystyle =}でなく {\displaystyle \equiv} を使う。)

これによって{\displaystyle b^{-1}}に対して{\displaystyle p}で割った余り（のようなもの）を定義できるようになった。

前提を踏まえて本問題を考える
  • 計算過程
    本問題では{\displaystyle m+n}から{\displaystyle n}を選ぶため、{\displaystyle _{m+n}C_n}における各項目のモジュラを求めれば良い。 {\displaystyle m+n}までの階乗の{\displaystyle 10^9+7}で割った余りとモジュラ逆数の２つテーブルを用意して、最後にそれぞれかけ算して{\displaystyle 10^9+7}のあまりを出せば良い。ただし、モジュラ逆数の導出には別の公式を使う必要がある。（証明は省く）

  • モジュラ逆数の導出

    {\displaystyle mod\ p}において{\displaystyle x}のモジュラ逆数は以下のように求まる。(ただし{\displaystyle p//x }は{\displaystyle p}を{\displaystyle x}で割った商)

    {\displaystyle x^{-1} \equiv -(p\%x)^{-1} \times (p//x)}

  • たどり着けないパターン

    • 連立方程式からも{\displaystyle m+n}が3の倍数じゃなかったら、0
    • {\displaystyle m, n}のどっちか一つでも負だったら、0
    • {\displaystyle m + n = 0}だったら、０

これで、重要なところの準備はできた。

コード

x, y = map(int, input().split())
# m = (i+2, j+1)
# n = (i+1, j+2)
# x = 2m + n
# y = m + 2n
# 2x - y = 3m
# 2y - x = 3n

m = (2*x-y) // 3
n = (2*y-x) // 3
def cmb(n, r, mod):
    if (r<0 or r>n):
        return 0
    r = min(r, n-r)
    return fac[n] * finv[r] * finv[n-r] % mod

mod = 10**9+7 #素数制限
N = m+n
# 階乗結果テーブル
fac = [1, 1] # モジュラテーブル
finv = [1, 1] # モジュラ逆数テーブル
finv_cal = [0, 1] #モジュラ逆数計算用

for i in range(2, N + 1):
    # 階乗のリストなので、計算されている一番後ろにかけて余りをとる。
    # ex: 4! = 3! * 4 
    fac.append((fac[-1] * i) % mod)
    # モジュラ逆数の導出の式
    finv_cal.append((-finv_cal[mod % i] * (mod//i)) % mod)
    # 階乗のリストなので、計算されている一番後ろにかけて余りをとる。  
    # ex 4!^-1 = 3!^-1 * 4^-1
    finv.append((finv[-1] * finv_cal[-1]) % mod)

# 行き先のx+yが3の倍数でないとたどり着けない。
if (x+y) % 3 != 0:
    print(0)
else:
    # m, n どちらかが負かもしくはどちらも0の時
    if m < 0 or n < 0 or (m+n) == 0:
        print(0)
    else:
        ans = cmb(m+n, n, mod)           
        print(ans)