ABC034C 経路

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

逆元

はじめに

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

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

問題

https://atcoder.jp/contests/abc034/tasks/abc034_c

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

方針

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

((W-1)+(H-1))!/((W-1)!(H-1)!) % MOD

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

逆元とは

aとmが互いに素である場合、mを法としてax≡1となるようなxが存在します（必要十分条件）。これをmを法とするaの逆元と言います。

逆元は複数存在し得ますが、xに対してさらにmを法とするとただ一つに定まります。この問題では合同式で計算が進むため、逆元は単一の整数と考えて問題はありません。

こちらを参考にさせていただきました。

整数の合同

フェルマーの小定理

pを素数として、pと互いに素な数aについて
a^(p-1)≡1が成立します。これをフェルマーの小定理と呼びます。

逆元と組み合わせて考える

さて、aとpは互いに素ですので、逆元a^(-1)を考えることができます。つまり、逆元をフェルマーの小定理を使うことで計算できます。
a^(-1)≡a^(p-2)

冪剰余

さて次はa^(p-2) mod pを求めれば良いですが、この問題ではpは巨大であるため、先にa^(p-2)を計算してから剰余を取ろうとすると、計算効率が著しく悪くなります。そこで、計算の最中に随時剰余の計算を行う必要があります。Pythonの場合は、この処理をpow(a,p-2,p)とすることで計算できます。

コード

MOD = 10**9+7
W, H = map(int, input().split())
W-=1 # コードを見やすくする
H-=1 # コードを見やすくする
mx = 2*10**5
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月1日
• 最終更新日：2020年5月9日