ケーキ同好会でも、プログラミングは必須スキルです！ 作：蒼(DPD)
望結ちゃんが条件を整理してくれたので、あとはこの漸化式の第$K$項を求めるだけになった。
下の漸化式は繰り返し二乗法で解けそうだけど、上の漸化式はどうだろう。
掛け算だけじゃなくて引き算もあるから、繰り返し二乗法だと難しそう。
「無理数出てくるかもしれないけど、一般項出してみる？」
「いや、多分この形だと、何かの$K$乗の形が出てくるからだめそう」
一般項だとだめなんだ。
あれ、なんかこのやり取りを過去にもしたことがあるような......？
「......漸化式を行列で表す？」
「それだ」
\begin{equation*}\begin{pmatrix}\text{res}_K \\x_K\end{pmatrix}=\begin{pmatrix}A\cdot\text{res}_{K-1} - B\cdot x_{K-1} \\C\cdot x_{K-1}\end{pmatrix}=\begin{pmatrix}A & -B \\0 & C\end{pmatrix}\begin{pmatrix}\text{res}_{K-1} \\x_{K-1}\end{pmatrix}\end{equation*}
「この形なら、行列累乗で解ける！」
\begin{equation*}\begin{split}\begin{pmatrix}\text{res}_K \\x_K\end{pmatrix}&=\begin{pmatrix}A & -B \\0 & C\end{pmatrix}\begin{pmatrix}\text{res}_{K-1} \\x_{K-1}\end{pmatrix}\\&=\begin{pmatrix}A & -B \\0 & C\end{pmatrix}\begin{pmatrix}A & -B \\0 & C\end{pmatrix}\begin{pmatrix}\text{res}_{K-2} \\x_{K-2}\end{pmatrix}\\&=\dots\\&=\begin{pmatrix}A & -B \\0 & C\end{pmatrix}^{K-1}\begin{pmatrix}\text{res}_1 \\x_1\end{pmatrix}\\&=\begin{pmatrix}A & -B \\0 & C\end{pmatrix}^{K-1}\begin{pmatrix}1 \\1\end{pmatrix}\end{split}\end{equation*}
行列累乗の前に、まず
黒マスの個数$A$、左右につながる部分の個数$B$、両側が個数$C$を求めないと。
上下につながって左右にはつながらない場合もあるから、忘れないようにそれも数える。
最初の部分だけでも実装量がかなり多いから、何度もデバッグしている時間はない。
望結ちゃんと有彩ちゃんは神妙な面持ちで私の後ろから画面をのぞき込んでいた。
import numpy as np
h, w, k = map(int, input().split())
s = [input() for _ in range(h)]
mod = 10**9 + 7
# 黒マスの個数: a
a = 0
for i in range(h):
a += s[i].count('#')
# 左右につながっている黒マスのペアの個数: b
b = 0
for i in range(h):
for j in range(w-1):
if s[i][j] == '#' and s[i][j+1] == '#':
b += 1
# 上下につながっている黒マスのペアの個数: b2
b2 = 0
for i in range(h-1):
for j in range(w):
if s[i][j] == '#' and s[i+1][j] == '#':
b2 += 1
# 両端が黒マスの行の個数: c
c = 0
for i in range(h):
if s[i][0] == '#' and s[i][w-1] == '#':
c += 1
# 両端が黒マスの列の個数: d
d = 0
for i in range(w):
if s[0][i] == '#' and s[h-1][i] == '#':
d += 1
# 上下左右に並べてつながる場合
if c > 0 and d > 0:
print(1)
exit()
# k = 0 の場合
if k == 0:
print(1)
exit()
# 上下左右に並べてもつながらない場合
if c == 0 and d == 0:
res = 1
k -= 1
while k > 0:
if k & 1:
res *= a
res %= mod
a *= a
a %= mod
k >>= 1
print(res)
exit()
# 上下に並べてつながる場合、90°回転させる
if d > 0:
b, b2 = b2, b
c, d = d, c
# 左右に並べてつながる場合
res = np.identity(2).astype(np.int64)
M = np.array([[a, -b], [0, c]], dtype=np.int64)
k -= 1
while k > 0:
if k & 1:
res = np.matmul(res, M) % mod
M = np.dot(M, M) % mod
k >>= 1
print((res[0][0] + res[0][1]) % mod)
お願い、これで合ってますように。
●
「お疲れ様！みんなすごいじゃん！！」
ひまり先輩とハイタッチした。いえーい！
最終的に、私たちはA問題からE問題、そしてI問題を解くことができた。
︙
5 algoRhythm 3300点
6 ケーキ同好会B 3200点
7 sum\_modP 3100点
︙
I問題を解いたのは、ケーキ同好会AB両チームだけだった。
「先輩方はどうでした？」
「全部解けたよ！」
順位表を見ると、先輩方のチームは6000点で、圧倒的な1位だった。
「これからもケーキ同好会を続けられるね！」
2か月前には、こんなにプログラミングが楽しいなんて思ってもみなかった。
コンテストが始まる前は不安で仕方がなかったけど、みんなで協力して問題が解けていく感覚はすごく楽しかった。
次もまたみんなでコンテストに出場したいな。
あ、とひまり先輩が声を上げた。
「そういえば、夏休みにしたいことがあったんだ！」
「何ですか？」
ひまり先輩は私たちの方を見て、笑顔を見せた。
「やっぱり夏と言えば合宿だよね！」