| Avito Cool Challenge 2018 |
|---|
| Закончено |
Chouti вспомнил о его первых днях в спортивном программировании. Когда он только научился писать сортировку слиянием, он подумал, что сортировка слиянием слишком медленная, поэтому он ограничил максимальную глубину рекурсии и модифицировал алгоритм следующим образом:
Chouti нашёл свою идею глупой, потому что, очевидно, эта «сортировка слиянием» иногда не может отсортировать массив правильно. Тем не менее, Chouti теперь хочет оценить, насколько его «сортировка слиянием» хороша. В частности, Chouti хочет узнать для случайной перестановки $$$a$$$ чисел $$$1, 2, \ldots, n$$$ математичекое ожидание числа инверсий после вызова MergeSort(a, 1, n, k).
Можно доказать, что математическое ожидание рационально. Для заданного простого числа $$$q$$$ допустим, что ответ может быть представлен как $$$\frac{u}{d}$$$ где $$$gcd(u,d)=1$$$. Выведите целое число $$$r$$$ удовлетворяющее $$$0 \le r<q$$$ и $$$rd \equiv u \pmod q$$$. Можно доказать, что такое $$$r$$$ существует и уникально.
В единственной строке записаны три целых числа $$$n, k, q$$$ ($$$1 \leq n, k \leq 10^5, 10^8 \leq q \leq 10^9$$$, $$$q$$$ — простое).
В единственной строке выведите число $$$r$$$.
3 1 998244353
499122178
3 2 998244353
665496236
9 3 998244353
449209967
9 4 998244353
665496237
В первом примере все возможные перестановки: $$$[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$$$.
При $$$k=1$$$, MergeSort(a, 1, n, k) вернет изначальную перстановку. Поэтому ответ равен $$$9/6=3/2$$$, и вы должны вывести $$$499122178$$$ потому что $$$499122178 \times 2 \equiv 3 \pmod {998244353}$$$.
Во втором примере все возможные перестановки это $$$[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]$$$ и соответствующие результаты вызова MergeSort(a, 1, n, k) это $$$[1,2,3],[1,2,3],[2,1,3],[1,2,3],[2,3,1],[1,3,2]$$$ соответственно. Поэтому ответ равен $$$4/6=2/3$$$, и вы должны вывести $$$665496236$$$ потому что $$$665496236 \times 3 \equiv 2 \pmod {998244353}$$$.
