해설서로 다른 재배열 중 정렬된 것은 정확히 하나이다. 앞에서부터 원소를 추가하며 현재 재배열 수를 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)이다.
