O - 文字列 Editorial by nok0
より高速な解法の概略を記します。
包除原理で解きます。
各文字種について、同じ文字が必ず隣接する個数を決め打つと、何個かの連結した成分に分けられます。分け方は、二項係数で求まります。後は、分けた成分をどのように並べるかを上手く求めたいです。
これは、指数型母関数の形で持ち、積を取ればよいです。任意 mod 畳み込みを用いると、freq の最大値を \(N\) として、\(\mathrm{O}(\sigma N \log^2(\sigma N))\) (\(\sigma\) は wordsize(26)) でこの問題を解くことが出来ました。
posted:
last update: