ABC357 :: 切腹倶楽部

3完。何もしてないのに入茶した。

C

提出一覧をコードサイズ順に見ていくと脳筋実装が多くて面白かった(小並)。なんかgzipで圧縮してる人もいた。あとcargo-atcoderの提出なんやこれ……。

コンテスト終了後に解説を見たときは全くわからんかったが，翌朝に読み直すと難しいことは言ってなかった。朝型の人間にABCはつらい。

以下，前提知識。

Note

冪乗の計算は普通に再帰でやると $\Omicron(n)$ だけど，ちょっと工夫すると $\Omicron(\log n)$ にできる。

a^n = \begin{cases} a & \text{if $n = 1$} \\ a \cdot a^{n-1} & \text{if $n > 1$ and $\mathrm{Odd}(n)$} \\ \left(a^\frac n2\right)^2 & \text{if $\mathrm{Even}(n)$} \end{cases}

このアルゴリズムの行列への応用，編入試に出てたんだよなぁ……。ああ逃れられない!(カルマ)

Note

こんな感じのやつ。俺習ってねーし……。

\begin{aligned} (a \bmod n) \bmod n &= a \bmod n \\ (a+b) \bmod n &= ((a \bmod n) + (b \bmod n)) \bmod n \\ ab \bmod n &= ((a \bmod n)(b \bmod n)) \bmod n \end{aligned}

$V_N$ の計算に繰り返し二乗法のアイデアを適用する。

$N$ の桁数を $K$ とすると， $N$ を $i$ 個つなげた整数 $f(N, i)$ は

f(N, i) = \begin{cases} N & \text{if $n = 1$} \\ f(N, i-1) \cdot 10^K + N & \text{if $n > 1$ and $\mathrm{Odd}(n)$} \\ f\left(N, \frac i2\right) \cdot 10^{\frac i2K} + f\left(N, \frac i2\right) & \text{if $\mathrm{Even}(n)$} \end{cases}

と表せる。剰余乗算の同一性より， $f(N, i) \bmod P$ は

f(N, i) \bmod P = \begin{cases} N \bmod P & \text{if $n = 1$} \\ (f(N, i-1) \cdot 10^K + N) \bmod P & \text{if $n > 1$ and $\mathrm{Odd}(n)$} \\ \left(f\left(N, \frac i2\right) \cdot 10^{\frac i2K} + f\left(N, \frac i2\right)\right) \bmod P & \text{if $\mathrm{Even}(n)$} \end{cases}

であり，いい感じに計算量を減らせる。

$V_N = f(N, N) \bmod P$ より，答えが出せる。

最初マジで何言ってんのかわからんかった。ていうか今でもわからん。

等比級数の和のmodを数学的にゴニョゴニョしてるんだろうなとガタイで分析。数学わからん。

累積和的にDFSすればいいらしい。そのうちやる。

そのうちやる。強連結成分分解って現実世界のどこで使われてるんだろう……。 Haskellの処理系で使われていることは知ってる。