【Python】繰り返し二乗法のまとめ

AtCoder

今回は、繰り返し二乗法について勉強したのでまとめたいと思います。

ちなみに、pythonでは組み込み関数powで繰り返し二乗法が組み込まれているので、自分で実装する必要はないようです。

組み込み関数 – Python 3.8.2 ドキュメント

例として、ここではAtCoder Beginner Contest156の問題Dを解きます。

繰り返し二乗法とは

310000000のように指数部分の数が大きい場合、下のように指数部分の数だけfor文を回す方法(計算時間O(N))だと、時間がかかってしまいます。

このような時、繰り返し二乗法を使うことで、計算時間をO(logN)まで短縮することができます。

繰り返し二乗法は、指数部分の自然数を2の累乗で表すことで計算を効率化させる手法です。

自然数は、

13 = 23 + 22 + 21

のように、2のべき乗の和で表すことができます。

例えば313は以下のように書くことができます。

313 = 32^3 + 32^2 + 32^1

こうすることで、指数部分のビットの数だけ計算を回せばよくなります。これをpythonで実装したコードは以下の通りです。

例題

例として、AtCoder Beginner Contest156の問題Dを解きます。

※ 上で、繰り返し二乗法の関数を実装しましたが、ここでは、pythonの組み込み関数powを使いたいと思います。

問題文

あかりさんは n 種類の花を 1 本ずつ持っています。

あかりさんは、これらの花から 1 本以上を選び、花束を作ろうとしています。

ただし、あかりさんは a と b の 2 つの数を苦手としていて、いずれかと一致するような本数の花からなる花束は作ることができません。

あかりさんが作ることのできる花束は何種類あるでしょうか。

(109+7) で割った余りを求めてください。

ここで 2 つの花束は、一方では使われているが、 もう一方では使われていない種類の花があるとき、別の種類の花束であるとみなします。

制約

  • 入力は全て整数である。
  • 2≤n≤109
  • 1≤a<b≤min(n,2×105)

方針

全ての花の組み合わせは、それぞれの花について「選ぶ」or「選ばない」の二択があり、また、全て選ばない時の1通りを除くので、2n – 1通りです。

ここから、a本の場合 (nCa)とb本の場合 (nCb)を除けばよいことになります。

制約より、2≤n≤109であるため、累乗の計算には繰り返し二乗法を用います。

組み合わせの計算

nCaの計算量を減らすために、以下のように式変形します。

\[ nCa = \frac{n!}{a!(n-a)!} = \frac{n*(n-1)*(n-2)*…*(n-a+1)}{a!} \]

余りを求める

計算途中で余りを求めるためには、nCaに含まれる割り算部分をかけ算に書き換える必要があります。

フェルマーの小定理より、p を素数、a を p の倍数でない整数として

\[ a^{p-1}\ \equiv\ 1\ (mod\ p) \]

が成り立ちます。

したがって、(109+7)は素数なので、

\[ a!^{(10^9+7)-1}\ \equiv\ 1\ (mod\ 10^9+7)\\ a!^{(10^9+7)-2}\ \equiv\ \frac{1}{a!}\ (mod\ 10^9+7) \]

となり、

\[ \frac{n*(n-1)*(n-2)*…*(n-a+1)}{a!}\\\equiv\ n*(n-1)*(n-2)*…*(n-a+1)*a!^{(10^9+7)-2}\ (mod\ 10^9+7) \]

と書けます。

余りの求め方については以下の記事が参考になりました。

「1000000007 で割ったあまり」の求め方を総特集! – 逆元から離散対数まで –  - Qiita

実装

タイトルとURLをコピーしました