ナイトのコマがある動きをするときに、目的の場所にたどり着けるかどうかという問題。連立方程式も使うし、高速にを計算する必要もある。結構内容としては盛りだくさんで難しい。久しぶりにモジュラ逆数について考えたので軽くまとめた。
概要
- ナイトの駒が座標
にいる。
- ナイトの駒は
にいるとき
か
の2パターンの動きしかできない。
- ナイトの駒を
まで移動させたいが、何通りある?
解くときに考えた内容
連立方程式
の行動回数を
、
の行動回数を
として考えると以下のように
を計算できる。
さえ計算できれば
を計算すればいい(早く)
ここが今回の課題で、における
を計算量少なく求めること。
nCrに関する前提
である
modに関する前提
において、足し算・引き算・かけ算が成立する。(
というのは
を
で割った余りのこと)
(例:
)
(例:
)
(演算結果が負の場合は演算結果とすれば良い)
(例:
)
- 割り算について一般化できるのか
これはモジュラ逆数というものである。直感的な話をすると、
において
で割るということは
掛けることであると同義であり、
である。
において、
とは何かというと、
が成立する値である。
- 例えば
において、
が成立するような
を考えると、
が割り切れた時の値。例えば
とすると
なので
で割り切れるので
(余りは一緒ということで合同という時は
でなく
を使う。)
これによってに対して
で割った余り(のようなもの)を定義できるようになった。
前提を踏まえて本問題を考える
- 計算過程
本問題ではから
を選ぶため、
における各項目のモジュラを求めれば良い。
までの階乗の
で割った余りとモジュラ逆数の2つテーブルを用意して、最後にそれぞれかけ算して
のあまりを出せば良い。ただし、モジュラ逆数の導出には別の公式を使う必要がある。(証明は省く)
モジュラ逆数の導出
において
のモジュラ逆数は以下のように求まる。(ただし
は
を
で割った商)
たどり着けないパターン
- 連立方程式からも
が3の倍数じゃなかったら、0
のどっちか一つでも負だったら、0
だったら、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)