解説相異なる並べ替えのうち整列済みのものはちょうど 111 個である。接頭辞の並べ替え数を WWW とする。iii 個目を加え、その値の頻度が ccc になったら W←W⋅i/cW\leftarrow W\cdot i/cW←W⋅i/c と更新し、最後に W−1W-1W−1 を出力する。接頭辞の並べ替え数は全体以下なので W≤1012+1W\leq10^{12}+1W≤1012+1。乗算も (1012+1)105<1.01⋅1017(10^{12}+1)10^5<1.01\cdot10^{17}(1012+1)105<1.01⋅1017 以下で符号付き64ビットに収まる。マップを使うと時間 O(NlogN)O(N\log N)O(NlogN)。
