競プロ初中級者100問

ABC145D Knight

この記事で使うアルゴリズム

逆元

はじめに

カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。

全問題の一覧はこちらです

問題

https://atcoder.jp/contests/abc145/tasks/abc145_d

この問題では逆元の計算が求められます。

方針

組み合わせの問題として解くことができます。 以下の値を計算すれば良いことになります。

1
2
3
W = X - ((X+Y)//3)
H = Y - ((X+Y)//3)
(W+H)!/(W!H!) % MOD

階乗の部分が巨大になるため、計算途中で剰余の計算を行います。しかしながら、除算が含まれるため逆元と呼ばれる概念を導入する必要があります。

逆元については以下の問題の解説をご覧ください。

ABC034C 散歩

ポイント

  • 移動可能な必要十分条件
    • 移動による座標の変化は(+1,+2)または(+2,+1)で、スタートは(0,0)であるため、X+Yは3の倍数である必要があります。
    • また、(+1,+2)の移動をn回繰り返した場合は(n,2n)に、(+2,+1)の移動をn回繰り返した場合は(2n,n)になることから、2min(X,Y) >= max(X,Y)である必要もあります。

コード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
MOD = 10**9+7
X, Y = map(int, input().split())
if (X > Y):
    X, Y = Y, X
if (X+Y)%3 != 0:
    print (0)
    exit()
if (2*X < Y):
    print (0)
    exit()
W = X - ((X+Y)//3)
H = Y - ((X+Y)//3)
mx = 10**6
fact = [1] * (mx+1) # 階乗を格納するリスト
def inv(n): # MODを法とした逆元
    return pow(n, MOD-2, MOD)
for i in range(mx):
    fact[i+1] = fact[i] * (i+1) % MOD # 階乗を計算
ans = (fact[W+H] * inv(fact[W]) * inv(fact[H])) % MOD # comb(W+H,W) = (W+H)!/(W!H!)
print (ans)

記事情報

  • 投稿日：2020年5月2日
  • 最終更新日：2020年5月8日