<!-- 註: このサイトはまだ工事中です -->

ABC357

{
  date: "",
}

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

C

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

D

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

以下,前提知識。

Note

繰り返し2乗法

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

an={aif n=1aan1if n>1 and Odd(n)(an2)2if Even(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

剰余乗算

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

(amodn)modn=amodn(a+b)modn=((amodn)+(bmodn))modnabmodn=((amodn)(bmodn))modn \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}

cf. 剰余演算 - Wikipedia

解法1: ユーザー解説のやつ

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

NNの桁数をKKとすると,NNii個つなげた整数f(N,i)f(N, i)

f(N,i)={Nif n=1f(N,i1)10K+Nif n>1 and Odd(n)f(N,i2)10i2K+f(N,i2)if Even(n) 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)modPf(N, i) \bmod P

f(N,i)modP={NmodPif n=1(f(N,i1)10K+N)modPif n>1 and Odd(n)(f(N,i2)10i2K+f(N,i2))modPif Even(n) 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}

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

VN=f(N,N)modPV_N = f(N, N) \bmod Pより,答えが出せる。

解法2: 公式解説のやつ

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

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

E

解法1: DFS

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

解法2: SCC

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