Будем считать число плохих перестановок, в конце вычтем его из $$$n!$$$ ($$$n!$$$ по модулю считается просто — если $$$n < m$$$, то считаем в лоб, иначе берём равным $$$0$$$). Будем добавлять числа в перестановку по очереди ($$$1, 2, ..., n$$$). Если мы добавляем число $$$i$$$, то у нас есть $$$i$$$ вариантов вставки, так как сейчас в перестановке $$$i - 1$$$ число. Назовём пару соседних элементов хорошей, если она отвечает требованию из условия ($$$x$$$ и $$$x + 1$$$). Пусть сейчас в перестановке $$$k$$$ хороших пар. Если мы вставим $$$i$$$ между индексами хорошей пары, то их количество уменьшится на $$$1$$$, если вставим после числа $$$i - 1$$$, то увеличится на $$$1$$$, иначе не изменится. Значит, для увеличения числа хороших пар на $$$1$$$ у нас есть $$$1$$$ вариант вставки, для уменьшения на $$$1$$$ есть $$$k$$$ вариантов, если мы не меняем ничего есть $$$n - k - 1$$$ вариант. После $$$n$$$ вставок мы хотим получить число хороших пар равное $$$0$$$, значит, увеличения и уменьшения разбиваются на пары. Будем искать сумму по всем вариантам вставок, приводящим к $$$0$$$ пар, без добавлений таких вариантов $$$(n - 1)!$$$ (по утверждению про количество ничего не меняющих перестановок). Рассмотрим первое увеличение, пусть оно было при числе $$$x$$$. До него было $$$0$$$ пар, поэтому количество перестановок равно $$$(k - 2)!$$$ (по числу ничего не меняющих вариантов вставки). На эту вставку у нас $$$1$$$ вариант. Заметим, что на следующую вставку (если она не меняющая) у нас будет $$$k - 1$$$ вариант, на вторую после нас будет $$$k$$$ вариантов, и так далее, то есть мы продолжили набирать факториал. Рассмотрим парное уменьшение (убрали именно эту пару), пусть оно было в момент $$$y$$$. У нас будет только $$$1$$$ вариант вставки, так как мы удаляем конкретную пару. Заметим, что из-за наличия пары (считаем, что она всего одна, для большего числа доказательство очевидно строится также, только надо аккуратно учитывать то, что будут другие удаления) до её удаления у нас было $$$y - 3$$$ варианта на предыдущей вставке, $$$1$$$ на текущей, а на следующей будет уже $$$y$$$, то есть множители $$$y - 2$$$ и $$$y - 1$$$ были удалены из факториала. Мы ищем сумму по всем вариантам оставшегося произведения после какого-то набора удалений пар подряд идущих чисел. Так как до $$$y$$$ есть $$$y - 1$$$ число, и любое из них могло быть в паре с $$$y$$$, то произведения без $$$y - 2$$$ и $$$y - 1$$$ будут учтены $$$y - 1$$$ раз, то есть мы просто удалили $$$y - 2$$$ из факториала. Таким образом, мы свели задачу к тому, что мы можем удалить любое подмножество множителей из $$$(n - 1)!$$$, при этом не можем удалять два подряд идущих числа (пары $$$y - 2, y - 1$$$ не могут пересекаться по разным $$$y$$$), нужно найти сумму по всем произведениям после удалений. Это легко делается с помощью ДП ($$$dp_0 = dp_1 = 1$$$, $$$dp_i = dp_{i - 2} * (i - 1) + dp_{i - 1} * i$$$, ответ — $$$dp_{n - 1}$$$) за $$$O(n)$$$ и набирает $$$77$$$ баллов. Теперь заметим, что после $$$m$$$ остатки по модулю зацикливаются. Разделим старое $$$dp$$$ на $$$dp1$$$ ($$$dp1_i$$$ — $$$i$$$ обязательно удалено) и $$$dp2$$$ ($$$dp2_i$$$ — $$$i$$$ может быть и удалено, и не удалено), будем считать значения ДП от $$$0$$$ до $$$m$$$. $$$dp1_i = dp2_{i - 2} * (i - 1)$$$, $$$dp2_i = dp2_{i - 1} * i + dp1_i$$$. Заметим, что все слагаемые, в которых не удалено одно из $$$m, 2m, ...$$$ равны $$$0$$$ и не влияют на сумму. Несложно доказать, что тогда ответ на задачу это $$$(dp1_m)^{\frac{n}{m}} * dp2_{n \pmod{m}}$$$. При использовании бинарного возведения в степень получаем решение за $$$O(m + log_2(\frac{n}{m}))$$$, которое набирает $$$100$$$ баллов. Все формулы в решении требовалось брать по модулю $$$m$$$.
P.S.: моё доказательство кажется мне чересчур сложным, вроде бы у ShinigamiCHOP есть доказательство проще.
