Good Bye 2018 D New Year and the Permutation Concatenation

https://codeforces.com/contest/1091/problem/D

ワが N(N+1)/2 というのは そのレツが ジュンレツであることと おなじ。(いいかえなくても おなじような はなしの ながれになる) N=10 で たとえば ふたつのジュンレツが つぎのように ならんでるとする。

AAAABBBBBB CCCCDDDDDD

BBBBBBCCCC がジュンレツであることは BBBBBB がコウジュンにソートされていないことに いいかえられる。なぜなら BBBBBB がコウジュンでなければ AAAABBBBBB < next(AAAABBBBBB)=CCCCDDDDDD <= AAAA + reverse_sort(BBBBBB) だから BBBBBBCCCC はジュンレツになっていて コウジュンであれば BBBBBB だけをならびかえても おおきくならないから CCCC に BBBBBB でつかわれてる かずを まぜないと いけなくて BBBBBBCCCC はジュンレツにならない。あとは このようなものの かずが わかればよく

\begin{align}
N!+\sum_{k=1}^{N-1} \left(N! - \frac{N!}{k!}\right)
\end{align}

により もとまる。


これ むずかしくないか。std::next_permutation のなかみを しってるひとなら おもいつきやすいかな。