みんなはちゃんと証明しましょう

文字列に含まれる文字の種類数を $\sigma$ とおきます。 $O(N2^{\sigma})$ で解きます。

AtCoderの提出詳細で見れるコードのタブ幅を 4 に変えるスクリプトを作りました。

$O(N)$ で解きます。

$O(N \log N)$ で解きます。

$O(M ^ 2)$ （一般の $N, M$ については $O(NM ^ 2)$ ）で解きます。

$O(N+M)$ で解きます。

\(O(N \log N)\) で解きます。

\(O(N )\) で解きます。

\(O( \log N )\) で解きます。

\(O(N)\) で解きます。

\(O(N \log K )\) で解きます。また、本問題の「与えられたグラフが巡回置換に分解できる」という特性をほとんど用いていないので、 \(P\) が順列でない場合でも少し書き換えるだけで解くことができます。

$O(\sqrt N)$ で解きます。