ケーキ同好会でも、プログラミングは必須スキルです！

ケーキ同好会11

$\require{color}$

問題文

非負整数$N$が与えられる。$2^N$を求めよ。

制約

入力はすべて整数

$1 \leq N \leq 10^{12}$

「例えば、$2^{100}$を計算しようと思ったら、何回2を掛け算をする必要がある？」

「100回ですか？」

「惜しい、小さい数でチェックしてみよう。2の1乗は何回？」

「あ、0回です。だから、$2^{100}$は99回ですね」

「正解！」

「じゃあ、今回は2の〈10の12乗〉乗を求めたいとします」

\[2^{10^{12}} = \ ?\]

ひまり先輩が書いた、一番右上の12がとても小さくなっている。

「この場合何回2を掛け算するんだっけ？」

「えっと、$10^{12} - 1$ 回です」

さっき間違えたので、慎重に答えた。

「正解！！」

「パソコンで$10^{12}$回掛け算しようと思ったら、とてつもなく時間がかかるんだよね」

「そうなんですか」

と望結ちゃんが言う。

「そうなんです」

と哀先輩が答える。

......なんか、望結ちゃんと哀先輩って似てるような気がする。

「$10^8$で1秒くらいだから、$10^{12}$だと一時間くらいだったかな？」

「一時間くらいなら待っててもいいんじゃないですか？他のことをしてるとか」

と望結ちゃんが言った。

「一つ求めるのに一時間かかったら、24個求めたら1日かかっちゃうよ！コンテストは長くても2～3時間だから、全然間に合わないね」

「あ、確かに」

「他のプログラムでも、例えば地図の経路案内で、目的地までの最短距離を求めるのに1時間かかってたら困るよね」

「歩いた方が速そうですね」

「そんな感じで、プログラムとしてはなるべく早く実行が終わる方が嬉しい」

「結論としては、最大128回の掛け算で計算できるよ」

「128回だとどれくらいの時間かかるんですか？」

「実行ボタンを押したら計算が終わってるくらいかな、どっちがいいかは比べるまでもないね」

「おーすごいです」

\[2^{1},\ 2^2,\ 2^4,\ 2^8,\ 2^{16}\]

こんな感じで、2の〈2のなんとか乗〉乗を先に求めておく。

例えば、$2^8$を計算したいときは、

\[2^8 = 2^{4+4} = 2^4 \cdot 2^4\]

みたいに、$2^4$を先に求めていたら一回の掛け算で計算できるよ。

同じように考えて、次の数字は前の数字の2乗で計算できるから、1回の掛け算で計算できるよ。

$2^2$は$2^1$の2乗、$2^4$は$2^2$の2乗、$2^8$は$2^4$の2乗、......

数を2乗していくのを繰り返していくから、「繰り返し二乗法」って言うんだよ。

$2^1$から$2^{2^{63}}$まで63回の掛け算で計算できるね。

「$2^{10^{12}}$はまだ求まってないんですよね？」

「そうだよ、ここまでは前計算！」

先に求めておいた数を使って、今から$2^N$を計算するよ。

例えば$2^{15}$を計算したいとしよう。

2の指数15を〈2のなんとか乗〉の足し算で分解するよ。

\[15 = 1 + 2 + 4 + 8\]

ここで、指数法則を使えば、

\[2^{15} = 2^{1+2+4+8} = 2^1 \cdot 2^2 \cdot 2^4 \cdot 2^8\]

みたいにすれば$2^{15}$を4回の掛け算で計算できるよ。

「なるほど......？」

「つまり2の$N$乗を求めたいとき、2を一回ずつ掛けていくより、代わりに8とか16を掛けた方が速く計算できる、ってこと？」

「そうそう」

「この、$15 = 1+2+4+8$って分解してる部分は、他の数でもできるんですか？」

「そうだよ！いい質問ですね、灰崎君」

どこかの教授のような声色でひまり先輩が言う。大学教授の真似、前もしてたけどひまり先輩の中で流行ってるのかな？

「結論から言うと、どんな数でも大丈夫だよ。いわゆる2進数ってやつだね」

\begin{eqnarray}15 &=& 1 + 2 + 4 + 8\\ &=& 1 \cdot 2^0 + 1 \cdot 2^1 + 1 \cdot 2^2 + 1 \cdot 2^3 \end{eqnarray}

っていうのは2進法の考え方だね。すべての自然数が2のなんとか乗の足し算で計算できるってやつだね。

2進法は10進法と違って、0と1の2種類の数字しか使わない数の表し方だよ。

これで整数を0から順に数えていくと、

\[0,1,10,11,100,101,110,111,1000,1001,1010,\dots\]

みたいになるから、2進法によって全部の自然数を表せてるね。

2進法での1桁目は1の位、2桁目は2の位、3桁目は4の位、みたいに呼ぶよ。

「それじゃあ、$2^N$を求めるときは、$N$を2進法で表すことが必要ですね」

「そうだね！」

それってプログラムでどうやるんだろう？〈2のなんとか乗〉の足し算で分解していくのはどうかな？

......なんか難しそう。

「実は、ゆいちゃんは似たことをもう実装したことがあるんだよ」

「え？」

「前回のPBCのD問題を思い出してみて」

えっと、D問題、D問題......。

あ、暗証番号の各桁の和だけ覚えてる、みたいな問題だった。ある数の1の位とか10の位を求めるのが難しかったね。

【挿絵表示】

......あれ、この方法って2進法でもできるんじゃない？

「$\texttt{%10}$で10進法のときの1の位が求まるから、$\texttt{%2}$で2進法のときの1の位が求まるんじゃないかな？......と思いました」

考えてたことが口から出てました。

2の位より上の部分を括弧でくくってみると、

\begin{eqnarray}15 &=& 1 + (2 + 4 + 8)\\ &=& 1 + 2\left(1 + 2 + 4\right)\end{eqnarray}

2の位より上の部分は2でくくれるから、2の位より上の位は2で割り切れて、あまりは1の位の値になる。

n = int(input())

while n > 0:

digit = n % 2

print(digit)

n = n // 2

【挿絵表示】

左から順に、1の位、2の位、4の位となっているから、6は2進数だと110になるんだね。

「繰り返し二乗法のプログラムはこんな感じかなー」

n = int(input())

res = 1

a = 2

while n > 0:

if n % 2 == 1:

res *= a

a *= a

n //= 2

print(res)

「$\texttt{a}$は2の〈2のなんとか乗〉乗を求めてるよ。

あとはゆいちゃんが書いた2進数のコードみたいに2進数の各桁を求めていって、桁が1のときに答え$\texttt{res}$に$\texttt{a}$をかけてるよ」

なるほど。掛け算を何回もするときは、こういうやり方で計算する回数を減らせるんだね。

「じゃあ、次は行列について話すね！」

●

行列っていうのは、数を長方形になるように並べたものだよ。

\begin{eqnarray}\begin{pmatrix} 1 & 2 \\ 3 & 4\end{pmatrix}, \begin{pmatrix}1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix},\begin{pmatrix}1 \\ 2 \\ 3\end{pmatrix}\end{eqnarray}

みたいなものは全部行列だよ。

行列には「行」と「列」があるよ。

行は横方向に並んでいる数字のことで、列は縦方向に並んでる数字のことだよ。

【挿絵表示】

【挿絵表示】

行列も、数みたいに足し算と掛け算ができるよ。

足し算は、同じところを足すだけだよ。

\begin{eqnarray}\begin{pmatrix} 1 & 2 \\ 3 & 4 \end{pmatrix} + \begin{pmatrix} 5 & 6 \\ 7 & 8 \end{pmatrix} = \begin{pmatrix} 1 + 5 & 2 + 6 \\ 3 + 7 & 4 + 8\end{pmatrix}=\begin{pmatrix} 6 & 8 \\ 10 & 12\end{pmatrix}\end{eqnarray}

掛け算は、ちょーっと難しいんだよね。

足し算と違って、行列の形が変わってしまうから。

\begin{eqnarray}\begin{pmatrix}1 & 2 & 3\end{pmatrix}\begin{pmatrix}4 \\5 \\6\end{pmatrix}=1 \cdot 4 + 2 \cdot 5 + 3 \cdot 6 = 32\end{eqnarray}

みたいに計算するよ。

行と列が増えても一緒だよ。

\begin{eqnarray}\begin{pmatrix}1 & 2 \\3 & 4\end{pmatrix}\begin{pmatrix}5 & 6 \\7 & 8\end{pmatrix}= \begin{pmatrix} 1 \cdot 5 + 2 \cdot 7 & 1 \cdot 6 + 2 \cdot 8 \\ 3 \cdot 5 + 4 \cdot 7 & 3 \cdot 6 + 4 \cdot 8\end{pmatrix}=\begin{pmatrix} 19 & 22 \\ 43 & 50\end{pmatrix}\end{eqnarray}

例えば1行1列の成分を求めたかったら、

左の行列の1行目と、右の行列の1列目の成分を掛けて足し合わせるんだよ。

「なんですか、これ」

「これが初めての人には難しいんだよねー」

「足し算みたいに、同じところを掛けるので良くないですか？」

「一応、そういう掛け算もあるんだけど、役に立つことが少ないからあんまり説明されないんだよね」

「まあ、とにかく難しい定義の方を使うと、行列がすごく便利になるんだよ」

「今からするみたいに、フィボナッチ数列の一般項を求めたりね」

行列の掛け算で難しいところは二つあるんだけど、一つは、掛け算ができるかどうかだね。

左の行列の列の数と、右の行列の行の数が同じでないとそもそも掛け算ができないよ。

\begin{eqnarray}\begin{pmatrix}1\\2\\3\end{pmatrix}\begin{pmatrix}1 & 2\\3 & 4\end{pmatrix}~~\leftarrow\text{そもそも掛け算できない！}\end{eqnarray}

この例だと、左の行列の列の数は1、右の行列の行の数は2で、違うから掛け算できないんだよね。

行列の積を勉強し始めたころは、まず行列の積を計算していいか確認するのが大変だったなー。

もう一つの難しいところは、具体的にどうやって計算すれば良いかってところだね。

さっき見たみたいに、行列の成分一つを計算するのに、掛け算と足し算をたくさんしないといけないし、そもそもどこを掛けたり足したりするかが最初は覚えにくいんだよね。

例えば、一行一列の成分を求めるときは、左の行列の一行目と、右の行列の一列目の成分を掛けて足し合わせるよ。

左の行列の一行目は赤色、右の行列の一列目は青色で書いてみたよ。

\begin{eqnarray}\begin{pmatrix} \textcolor{red}{1} & \textcolor{red}{2} \\ 3 & 4\end{pmatrix} \begin{pmatrix} \textcolor{blue}{5} \\ \textcolor{blue}{6} \end{pmatrix}= \begin{pmatrix} \textcolor{red}{1} \cdot \textcolor{blue}{5} + \textcolor{red}{2} \cdot \textcolor{blue}{6} \\ 3 \cdot 5 + 4 \cdot 6 \end{pmatrix} = \begin{pmatrix} 17 \\ 39 \end{pmatrix}\end{eqnarray}

同じようにして、一行二列の成分を求めるときは、左の行列の二行目と、右の行列の一列目の成分を掛けて足し合わせるよ。

\begin{eqnarray} \begin{pmatrix} 1 & 2 \\ \textcolor{red}{3} & \textcolor{red}{4}\end{pmatrix} \begin{pmatrix} \textcolor{blue}{5} \\ \textcolor{blue}{6} \end{pmatrix}=\begin{pmatrix} 1 \cdot 5 + 2 \cdot 6 \\ \textcolor{red}{3} \cdot \textcolor{blue}{5} + \textcolor{red}{4} \cdot \textcolor{blue}{6} \end{pmatrix} = \begin{pmatrix} 17 \\ 39 \end{pmatrix}\end{eqnarray}

でも、これを覚えるのはなかなか大変だよね。左目は行方向、右目は列方向に動かすと目が回りそう。

右側の行列を上に持っていくと、縦と横がきれいにそろうから覚えやすいかもしれないね。

【挿絵表示】

あと、この覚え方だと計算した後の行列の大きさが分かりやすくなるのもポイントだね。

「え、すごい分かりやすくなりました」

「でしょー」

「じゃあ、今までの知識を総動員して、フィボナッチ数列の一般項を求めよう！」

フィボナッチ数列の漸化式から、一般項$F_n$を行列を使って求めるよ。

まず、$F_0 = 0, F_1 = 1$ として、

\[F_{n+1} = F_n + F_{n-1}\] という漸化式が成り立つよ。

これを行列を使って表すと、

\begin{eqnarray}\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix}\end{eqnarray}

となるよ。

「え、漸化式を行列で表す？？」

「式変形としてはこんな感じかなあ」

\begin{eqnarray}\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} F_n + F_{n-1} \\ F_n \end{pmatrix} = \begin{pmatrix} 1\cdot F_n + 1\cdot F_{n-1} \\ 1\cdot F_n + 0\cdot F_{n-1} \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix}\end{eqnarray}

「でも、下の行は$F_n = F_n$になってて同じだから要らないんじゃないですか？」

「おっ、ちゃんと自分で確かめてて偉いねー」

「下の行を入れることで、行列が正方行列になるようにした」

「正方行列？」

「行の数と列の数が同じの行列」

名前の由来は正方形みたいな形だからなのかな？

これからが面白いんだけど、この式を自分自身に使ってみるよ。

\begin{eqnarray}\begin{split} \begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_n \\ F_{n-1} \end{pmatrix}\\ &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix} \begin{pmatrix} F_{n-1} \\ F_{n-2} \end{pmatrix}\\ &= \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^2 \begin{pmatrix} F_{n-1} \\ F_{n-2} \end{pmatrix}\end{split}\end{eqnarray}

数字と同じで、行列でも同じもの同士を掛け算したときは、2乗と同じ感じで書けるよ。

あとは、これを何回も繰り返していくよ。

\begin{eqnarray}\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \dots = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} F_1 \\ F_0 \end{pmatrix} = \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1\\ 0 \end{pmatrix}\end{eqnarray}

$F_1$と$F_0$は$F_0 = 0 , F_1 = 1$だったから、その値を入れたよ。

「ここまでやったら、あとはどうすれば良いか分かる？」

「えーっと？」

「$n$乗を高速に求める方法はー？」

「あ、繰り返し二乗法？！」

「正解！！」

これは何とかの$n$乗の形になってるから、繰り返し二乗法を使えば高速に計算できるね。

行列\begin{eqnarray}\begin{pmatrix}1 & 1 \\ 1 & 0\end{pmatrix}^n\end{eqnarray}を繰り返し二乗法で求めた結果を\begin{eqnarray}\begin{pmatrix} a & b \\ c & d\end{pmatrix}\end{eqnarray}っておいてみると

\begin{eqnarray}\begin{pmatrix} F_{n+1} \\ F_n \end{pmatrix} = \begin{pmatrix} a & b \\ c & d \end{pmatrix} \begin{pmatrix} 1 \\ 0 \end{pmatrix} = \begin{pmatrix} a \\ c \end{pmatrix}\end{eqnarray}

ってできるよ。

一番左と一番右の行列の各成分は等しくなるから、

\[F_n = c\]

つまり、フィボナッチ数列の第$n$項$F_n$は、行列\begin{eqnarray}\begin{pmatrix} 1 & 1 \\ 1 & 0\end{pmatrix}^n\end{eqnarray}の2行1列の成分$c$になるよ。

なんとなく分かったような分からないような。

まだ行列に慣れてないから、ちょっと難しいかも。

私の頭から煙が出始めているのをみて、哀先輩が言った。

「一回休憩しようか」

「今日はマカロンだよ！楠(くすのき)先生にもらったんだ！」

とりあえずいったん休憩して頭をリフレッシュ。この部活がケーキ同好会で良かった。もしプログラミング同好会だったら、私の頭は今頃過負荷で焼き切れているところだった。

●

「行列累乗のコードはこうなるよ」

import numpy as np

n = int(input())

fib = np.array([[1, 1], [1, 0]])

a = fib.copy()

while n > 0:

if n % 2 == 1:

fib = np.matmul(fib, a)

a = np.matmul(a,a)

n //= 2

print(fib[1][0])

「$\texttt{import numpy as np}$っていうのは何ですか？」

「行列をPythonで扱うために必要なものだよ」

「$\texttt{np.array}$というのが行列」

「宣言の所が難しいけど、他は配列と同じで、$\texttt{[]}$を使って要素にアクセスできるよ」

「$\texttt{np.array}$を使えば、難しい行列の掛け算を自分で実装せずに、$\texttt{matmul(A, B)}$で行列の掛け算をすることができる」

へえー、便利だね。行列の掛け算自体にまだ慣れてないけど、これなら使いやすそう。

$\texttt{matmul}$が掛け算をしているってことを知っていたら、していることは繰り返し二乗法とおんなじだね。

●

「失礼します、部活の見学に来ましたー、あ！ゆいじゃん」

やっほー、と言って部室に入ってきたのは桜井さんだった。

「ほんとにスイーツ食べてるんだ」

「桜井さん、ちょっと引いてるニュアンス入ってない？！」

いや、冷静になると、学校でマカロン食べてる方がおかしいかも。

「......有彩って呼んでよ。なんかこそばゆいから」

「わかった」

呼び捨てはちょっと抵抗あるから、有彩ちゃんって呼ぶことにした。

1年生三人で向かい合って座った。

あ、哀先輩が悪い顔してる。

「6月のコンテスト、一年生3人で出てみたら？」

「ケーキのコンテスト？」

有彩ちゃんが首を傾げた。

かくかくしかじか。

「ケーキ同好会っていう名前なのに、プログラミングの大会に出るんだ」

へえー、といったように有彩ちゃんが言った。

「私プログラミング少しならできますよ、ロボ部に入るつもりだったんで」

「そうなんだ！ありさちゃんすごいね！」

ひまり先輩が有彩ちゃんを褒めてる。

「私は、やってないけど」

恐る恐るといった感じで、望結(みゆ)ちゃんが言った。

「大丈夫！一か月もあれば基本文法はマスターできるし、みゆちゃんは数学が好きなら絶対向いてるよ！」

ひまり先輩って、他の人に対してネガティブなことをほとんど言わないよね。ひまり先輩といっしょにいると、自分も前向きになれる気がする。

「分かった、善処する」