ケーキ同好会でも、プログラミングは必須スキルです！ 作：蒼(DPD)
I - Fraction of Fractal
実行制限時間:$2$sec/メモリ制限:$256$MB
配点:$1700$点
問題文
$H\times W$のグリッドが与えられ、各マスは白または黒で塗られています。
この盤面をレベル1のフラクタルと定義します。
レベル0のフラクタルは、黒いマス1つだけからなる$1\times 1$のグリッドです。
レベル$k + 1$のフラクタルとは、レベル$k$のフラクタルを、グリッドのすべての黒いマスに相当する位置に並べ、
白いマスに相当する位置は白いマスで埋めたものと定義します。
入力として整数$K$が与えられるので、レベル$K$のフラクタルにおいて黒マスからなる連結成分の個数がいくつあるか求めてください。
答えは非常に大きくなる可能性があるので、$10^9+7$で割った余りを出力してください。
制約
$1 \leq H, W \leq 10^3$
$0 \leq K \leq 10^{18}$
入力形式
$H\ W\ K$
$s_{11}\dots s_{1W}$
$\vdots$
$s_{H1}\dots s_{HW}$
入力例1
\small
$\texttt{3\ 3\ 3}$
$\texttt{.\#.}$
$\texttt{\#\#\#}$
$\texttt{\#.\#}$
出力例1
$\texttt{20}$
入力例2
$\texttt{3 3 3}$
$\texttt{\#\#\#}$
$\texttt{\#.\#}$
$\texttt{\#\#\#}$
出力例2
$\texttt{1}$
入力例3
$\texttt{11 15 1000000000000000000}$
$\texttt{.....\#.........}$
$\texttt{....\#\#\#........}$
$\texttt{....\#\#\#\#.......}$
$\texttt{...\#\#\#\#\#\#......}$
$\texttt{...\#\#\#\#\#\#\#.....}$
$\texttt{..\#\#.\#\#\#.\#\#....}$
$\texttt{..\#\#\#\#\#\#\#\#\#\#...}$
$\texttt{.\#\#\#.....\#\#\#\#..}$
$\texttt{.\#\#\#\#...\#\#\#\#\#\#.}$
$\texttt{\#\#\#\#\#\#\#\#\#\#\#\#\#\#\#}$
$\texttt{\#.\#\#..\#\#..\#\#..\#}$
出力例3
$\texttt{301811921}$
出典: AtCoder Grand Contest 003
例えば、これが入力で与えられたとする。
入力で与えられた模様をレベル1のフラクタルという。
この模様から作ったレベル2のフラクタルはこうなる。
レベル1のフラクタルの黒マスがあるところに、前のレベルのフラクタルを置くと、次のレベルのフラクタルになる。
フラクタルのレベルが$K$になるまで、これを繰り返していく。
フラクタルのレベルが$K$になったときの、黒マスからできる連結成分の個数を数える問題。
連結成分は、上下左右につながっているマスの集まりのこと。
斜めにつながっているマスは連結していることにしないことに注意して。
連結成分が1個
連結成分が3個
さっきの例に戻ると、このフラクタルは何回続けても上下左右につながっていることが分かる。
だから$K$が何だとしても連結成分は1つだけ。
一般に、上下左右につながるレベル1のフラクタルから作った、より上のレベルのフラクタルも上下左右につながっていることまでは分かった。
つまり、入力で与えられたレベル1のフラクタルを並べて上下左右につながるなら、
$K$がどんな大きさでも連結成分は1つだけ。
フラクタルを上下左右に並べてつながるとき
\[\text{res} = 1\]
「はい、質問、フラクタルを並べて上下左右につながるときってどうやって判定するの？」
「両端が黒マスになっている行が存在することを調べたらいいと思ってる」
横に並べてつながる
横に並べてもつながらない
「じゃあ、フラクタルを上下に並べてつながるときは、ある列の両端が黒マスかな」
「そうだね」
じゃあ上の例のフラクタルは、左から2列目の両端が黒マスだから、上下に並べてもつながるってことだね。
フラクタルを左右に並べてつながる $\Leftrightarrow$ ある行の両端が黒マス
フラクタルを上下に並べてつながる $\Leftrightarrow$ ある列の両端が黒マス
「じゃあ次は、フラクタルを上下左右に並べてもつながらないときを考えてみよう」
上下左右につながらない、レベル1
このフラクタルが入力で与えられたとしたら、レベル2のフラクタルはこうなる。
上下左右に並べてもつながらないから、レベル1のフラクタルがそのまま連結成分になる。
つまり、レベル1のフラクタルの個数が答えになる。
「レベル$K$のフラクタルって、レベル1のフラクタルを何個含んでるの？」
「レベル1のフラクタルの黒マスの個数を$A$とすると、
レベル$K$のフラクタルはレベル$K-1$のフラクタルを$A$個含んでる。
だからレベル1のフラクタルを$A^{K-1}$個含んでる」
「えーっと......？」
「漸化式を何回も使う」
レベル$K$のフラクタルについて、含まれているレベル1のフラクタルの個数を$\text{res}_K$と書く。
レベル$K$のフラクタルは、自分より1つ下のレベルのフラクタルを$A$個持っている。
\[\text{res}_K = A\cdot \text{res}_{K-1}\]
この漸化式をレベル1になるまで繰り返し適用すると、
$$\begin{equation*}\begin{split}\text{res}_K &= A\cdot\text{res}_{K-1} \\&= A\cdot\left(A\cdot\text{res}_{K-2}\right)\\&= A^2\cdot\text{res}_{K-2}\\&= \dots\\&= A^{K-1}\cdot\text{res}_1\\&= A^{K-1}\end{split}\end{equation*}$$
フラクタルを上下左右に並べてもつながらないとき
レベル1のフラクタルの黒マスの個数を$A$と書くと、
\[\text{res} = A^{K-1}\]
「なんか解けそうじゃない？」
「繰り返し二乗法で解ける！」
同じ数を何回もかけるときは、繰り返し二乗法を使えば高速に計算できるはず。
「じゃあ、あと考えないといけない条件は二つ。
上下に並べてつながるけど、左右に並べてもつながらないフラクタルと、
上下に並べてもつながらないけど、左右に並べるとつながるフラクタル」
上下に並べてつながる
左右に並べてつながる
残り時間はあと30分ほどだった。
実装する時間を考えると、あと15分くらいでこの問題を解きたい。
でも、あと二つだと間に合わなさそう。
さすがに無理そうな雰囲気に呑まれそうだったとき、有彩ちゃんがパチンと指を鳴らした。
「どっちかだけ考えてもいいんじゃない？
ほら、上下に並べてつながるフラクタルを90°回転させたら、
左右に並べてつながるフラクタルになるじゃん」
上下に並べてつながる
時計回りに90°回転させた
「ほんとだ、すごい！」
「じゃあ、左右に並べてつながらないやつは、90°回転して左右につながるようにしようか。
つまり、あと考えればよいのは左右につながって、上下につながらないやつだけ」
なんとか間に合いそうな気がしてきた。でもまだぎりぎりだから、気は抜けない。
具体的に、入力例1で考えてみよう。
これは左右に並べた時だけつながるレベル1のフラクタルで、黒マスの個数$A$は$A=6$だね。
じゃあ、これのレベル2のフラクタルを考えてみよう。
連結成分の個数は4個。
上下左右につながらない場合は$A$と等しい$6$個になるはずだから、
それと比べて連結成分は2つ減ってる。
「連結成分が減ったってことは、連結成分が横並びになったところで合体してるってことだよね」
「そうか、じゃあ減った連結成分の個数は、
レベル1のフラクタルで横につながってる部分の個数と同じ数か」
レベル1のフラクタルで左右につながってる部分に青色で線を描いて、
レベル2のフラクタルの方にも、連結成分が合体した部分に青色で線を描いてみた。
確かに、二つの個数は等しくなるね。
「さらに、レベル$K$のフラクタルに含まれている、レベル$K-1$のフラクタルが左右に連結する個数とも同じになる。
......この量は大事そうだから、$B$とおこう」
「じゃあ、次はレベル3のフラクタルを描く？」
「いや、サイズが大きすぎて時間に間に合わない」
私はもう少し良い方法を思いついた。
「上下にはつながらないんだから、レベル2のフラクタルを左右に置く場合だけ考えてみない？」
「連結成分の個数は4の2倍から1減って7個になるはずだよ」
いや、もっと減ってるかも。
数えてみると、連結成分の個数は6個だった。
「あれ？
レベル2のフラクタルが左右に並んだとき、連結成分の減る量って1個じゃなくない？」
レベル2のフラクタルが左右に並んだときに初めてつながる部分にオレンジ色で線を引いた。
「ほんとだ、2個だね」
望結ちゃんが私の書いた図を見て、頷いた。
一般的に、レベル$K$のフラクタルを左右に並べたとき、減る連結成分の個数を$x_K$と書こう。
このとき、答えの漸化式はこうなる。
\[\text{res}_K = A\cdot\text{res}_{K-1} - B\cdot x_{K-1}\]
レベル$K$のフラクタルにおいて、レベル$K-1$のフラクタルが左右につながる部分の個数は$B$個だから、
その分$B\cdot x_{K-1}$を引いた。
後は$x_K$の求め方を考えればいい。まずは、簡単な例から考える。
レベル1のフラクタルを左右に並べてみよう。
今考えているレベル1のフラクタルは、左右に並べたら必ずつながるので、減少する連結成分は1個。
つまり、$x_1=1$になる。
次は、$x_2$を考えてみよう。
レベル$K$のフラクタルにおいて、
行の両端にレベル1のフラクタルがある分だけ連結成分が減ってることが分かる。
つまり、$x_{K}$は、レベル$K$のフラクタルで、レベル1のフラクタルが両端にある行の個数と同じになる。
レベル1のフラクタルにおける両端が黒の行の個数を$C$とおいて、$x_K$を求める。
レベルが1上がるごとに両端のレベル1フラクタルの個数は$C$倍になるから、
$x_K$の漸化式はこうなるね。
\[x_K = C\cdot x_{K-1}\]
$x_K$も求められた。これまでのことをまとめよう。
$$\begin{equation*}\left\{\begin{aligned}\text{res}_K &= A\cdot\text{res}_{K-1} - B\cdot x_{K-1} \\x_K &= C\cdot x_{K-1}\end{aligned}\right.\end{equation*}$$