AtCoder Beginner Contest 335(Sponsored by Mynavi)
新年一発目。なかなか大変な新年となっているが。
最短距離を求めたいならDijkstraなどが使えるが、この問題ではいわば「最長距離」を求めたい。
Dijkstraで“最短”距離が求まるのは、$v$ がキューから取り出された時点で、 もう他のルートで $v$ の今の値よりよい値になるルートはないことが確定しているから。
最長距離の場合、「未探索の迂回ルートで後から更新されうる」可能性がある。
最長路だと思って $u→v$ に探索を広げた後、実は $u$ にもっと長く辿り着けるルートが後から見つかりました、となったら、
$v$ 以降も全て探索しなおしとなり、何回も更新が発生してTLEとなる。
ただ、今回の場合、通るルートが広義単調増加という制約から、上手く評価値を設定することで 「キューから取り出された時点で確定している」ようにできる。
Dijkstraで、キューに入れる値を $(A_v, 暫定種類数 \times -1, v)$ として、小さい方から取り出せばよい。
いま、$(A_v,-S_v,v)$ がキューから取り出されたとして、
よって、もう $v$ に関して $S_v$ が更新されることはない。
この評価値でDijkstra(っぽいこと)を行うことで、$v$ がキューから取り出された時点で、それが最長の $S_v$ だと確定できる。
愚直には、以下のDPで求められる。
$DP[1]=1$ として、$i=1,2,3,...$ について そこから移動可能なマス $j=i+A_i,i+2A_i,...$ に $DP[j]+=DP[i]$ としていけば、最終的な $\sum_i{DP[i]}$ が答えとなる。
$A_i$ が大きい場合は移動先の候補が少ないので素直に更新できるが、$A_i$ が小さいと移動先が多く、TLEとなる。
こういうときは平方分割。
以下の2つのデータに分けて状態数を管理する。
$d$ は、上限を約 $\sqrt{N}$($=L$ とする)あたりにしておく。
$i$ を遷移元とする場合、その時点の $DP'[i]$ と、 $\displaystyle \sum_{d=1}^{L}Added[d][i \% d]$ の合計が、本来の $DP[i]$ となる。
で、遷移先への加算は、
とすると、全部で $O(N\sqrt{N})$ で答えが求められる。
原始根を利用すると、累乗がすごろくになる。
P = 13, 原始根 r = 2 e 0 1 2 3 4 5 6 7 8 9 10 11 | 12 13 ... 2^e % P 1 2 4 8 3 6 12 11 9 5 10 7 | 1 2 ...
13に対して2は原始根の1つなので、$2^0,2^1,2^2,...,2^{11} \mod{13}$ は $1~12$ を一巡する。
この上で $A_i=3$ を考えると、$2^e=3$ となるのは $e=4$ なので、$3^k$ は上記の表を4ずつ進むループ状のすごろくとなる。
e 0 1 2 3 4 5 6 7 8 9 10 11 | 12 13 ... 16 ... 2^e % P 1 2 4 8 3 6 12 11 9 5 10 7 | 1 2 ... 3 3^0 3^1 3^2 3^3 3^4 ... ↓↓↓ k 0 1 2 3 4 ... 3^k % P 1 3 9 1 3 ...
もう一例、$A_i=5$ を考えると、$e=9$ なので、$5^k$ は上記の表を9ずつ進む。
e 0 1 2 3 4 5 6 7 8 9 10 11 | 12 13 ... 18 | ... 27 ... | 36 ... 2^e % P 1 2 4 8 3 6 12 11 9 5 10 7 | 1 2 ... 12 | ... 8 ... | 1 ... 5^0 5^1 5^2 5^3 5^4 ... ↓↓↓ k 0 1 2 3 4 5 ... 5^k % P 1 5 12 8 1 5 ...
すごろくは $P-1=12$ 周期なので、$A_i=2^e$ とした時、 $A_i^k$ は、$GCD(e,12)$ の倍数のマスは全て止まり、それ以外は止まらない、ということになる。
e 0 1 2 3 4 5 6 7 8 9 10 11 | 12 13 ... r^e % P 1 2 4 8 3 6 12 11 9 5 10 7 | 1 2 ... 3^k が止まる * * * * e=4、GCD(4,12)=4 5^k が止まる * * * * * e=9、GCD(9,12)=3
なので、$A_i=2^{e1},A_j=2^{e2}$ として、「$GCD(e_1,12)$ が $GCD(e_2,12)$ の約数なら、$e_1$ ずつ進むすごろくは $e_2$ のマスに止まる」ということになる。
これを言い換えると、元の条件である「$A_i^k \equiv A_j \mod{13}$ となる $k$ が存在する」ことになる。
各 $A_i$ に対して $e_i$、ひいては $GCD(e_i,P-1)$ がわかればよい。
これは $P-1$ の約数なので、種類数は限られる。
$GCD(e,P-1)$ ごとに個数をカウントしておくと、種類数を $L$ として、$O(L^2)$ かけて組合せを総当たりして間に合う。
とはいえ、まず $P$ の原始根を求めるのってそれなりに計算量がかかるし、さらに $A_i$ がその何乗か $e$ を求めるのも大変。
なので、原始根や $e$ は明示的には求めないで、直接 $GCD(e,P-1)$ を求める工夫が必要となる。
位数を求める。
$a^0,a^1,...$ がどんな周期で“1”に戻るかを示す値だが、必ず $P-1$ の約数となる。
たとえば $P=28001$ として、$P-1$ を素因数分解し、$2^5 5^3 7^1$ となったとする。
$A_i=20$ の位数を求めるとする。以下、mod P は省略する。
20^28000 は必ず 1 (フェルマーの小定理) 2の素因数について 20^14000 が1か調べる → 1 20^ 7000 が1か調べる → 1 20^ 3500 が1か調べる → 1 20^ 1750 が1か調べる → 1 20^ 875 が1か調べる → not 1 → 長くとも 1750 周期で1になる 5の素因数について 20^ 350 が1か調べる → not 1 → 5については周期を更新できず、1750周期のまま 7の素因数について 20^ 250 が1か調べる → not 1 → 20の位数は 1750 とわかる
で、$GCD(e,P-1) = \dfrac{P-1}{位数}$ となるので、つまり $A_i=20$ に対する $GCD(e,P-1)$ は「$28000/1750=16$」となる。
1つの $A_i$ につき、$P-1$ の素因数の個数は $O(\log{P})$、累乗を計算するのに $O(\log{P})$ かかるので、$O((\log{P})^2)$ かかる。
時間制限は長めなので、これで間に合う。