Divisible Permutation

2 secs 1024 MB
mel1's icon mel1

出典:2022年日本数学オリンピック予選問題9

各頂点が 11 以上 NN 以下の整数に対応するような NN 頂点の有向グラフを考えます. iji\mid jのとき, 頂点 ii から頂点 jjへの有向辺があるとします.

m=1N(頂点mから頂点Nに至る経路の数)\displaystyle\sum_{m=1}^{N} \left( 頂点mから頂点Nに至る経路の数 \right) がこの問題の答えになります.

頂点 NN に至れるような頂点は NN の約数に対応するような頂点しかなく, 制約の範囲内では高々 240240 個です. したがって, NN の約数を列挙してからこの経路数をDPなどで求めれば, 実行時間制限内に収まります. NN の制約が N109N\leqq10^9 などでもこの方針で十分通ると思います.

(頂点の数を絞らなくても, 辺の本数のオーダーが O(NlogN)\mathcal{O} \left(N\log N \right)なので, 時間計算量もこのオーダーとなり, 間に合うと思います......)


経路 v1v2vkv_1 v_2\ldots v_k が, 順列 Pvi=vi+1 (1ik1),PN=v1,Pi=i (iは経路に現れない)P_{v_i} = v_{i+1} \ (1\leqq i \leqq k-1), P_N = v_1, P_i = i \ (iは経路に現れない) に対応します.