Python3で解く AtCoder Beginner Contest 145 D - Knight
ナイトのコマがある動きをするときに、目的の場所にたどり着けるかどうかという問題。連立方程式も使うし、高速にを計算する必要もある。結構内容としては盛りだくさんで難しい。久しぶりにモジュラ逆数について考えたので軽くまとめた。
概要
- ナイトの駒が座標にいる。
- ナイトの駒はにいるとき かの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)