Привет, Codeforces!

Мы с SomethingNew рады пригласить вас на CodeTON Round 6 (Div. 1 + Div. 2, Rated, Prizes!), который пройдёт в 18.09.2023 17:35 (Московское время). У вас будет 2 часа 15 минут на решение 8 задач. Раунд будет рейтинговым для всех.

Мы хотим выразить благодарность:

• 74TrAkToR за координацию раунда.
• isaf27, ugly2333, JianfengZhu, Little09, bashkort, Kieray, fishy15, Vladithur, Dart-Xeyter, pakhomovee, makrav, meowcneil, 127.0.0.1, Nanani, nnv-nick, SomethingDifferent, vl342, shiv_codegen, M1lkas, allmath, sdyakonov за тестирование раунда и полезный фидбэк.
• MikeMirzayanov за системы Codeforces и Polygon.

Разбалловка:

500 — 750 — 1500 — 1750 — 2750 — 3250 — 3250 — 4000

Мы надеемся, что наши задачи будут интересными для вас!

Разбор

Поздравляем победителей!

1. orzdevinwang
2. cnnfls_csy
3. jiangly
4. PubabaOnO
5. maspy
6. tourist
7. AoLiGei
8. Um_nik
9. noimi
10. Geothermal

Информация от спонсора этого раунда:

Hello, Codeforces!

We, the TON Foundation team, are pleased to support CodeTON Round 6.

The Open Network (TON) is a fully decentralized layer-1 blockchain designed to onboard billions of users to Web3.

Since July 2022, we have been supporting Codeforces as a title sponsor. This round is another way for us to contribute to the development of the community.

The winners of CodeTON Round 6 will receive valuable prizes.

The first 1,023 participants will receive prizes in TON cryptocurrency:

• 1st place: 1,024 TON
• 2–3 places: 512 TON each
• 4–7 places: 256 TON each
• 8–15 places: 128 TON each
• …
• 512–1,023 places: 2 TON each

We wish you good luck at CodeTON Round 6 and hope you enjoy the contest!

Привет, Codeforces!

Мы с SomethingNew рады пригласить вас на Codeforces Round 814 (Div. 1) и Codeforces Round 814 (Div. 2), которые пройдут во 16.08.2022 17:35 (Московское время). У обоих дивизионов будет по 6 задач и 2 часа на их решение.

Мы хотим выразить благодарность:

• 74TrAkToR за отличную координацию раунда и идею одной из задач для Div. 2.
• pakhomovee за идею и подготовку одной из задач для Div. 1, а также за тестирование остальных задач раунда.
• Um_nik, 244mhq, turmax, fedoseev.timofey, errorgorn, FairyWinx, daubi, arbuzick, AlesyaIvanova, Dart-Xeyter, Alexdat2000, Vladithur, rafaelka, plagues, LeoRiether, satyam343, ilya.kligunov, 1024mb, 127.0.0.1, efimovpaul, Prokhor08, marzipan, kirill.kligunov, MirMak, dmitry.lisitsyn, MichsSS, PUFL, bpaT_Kapaca, RomkaRS за тестирование раунда и полезный фидбэк.
• MikeMirzayanov за системы Codeforces и Polygon.
• ilaburkov за то, что он существует.

Разбалловка:

Div. 2: 500 — 1000 — 1250 — (1250 — 1000) — 2500 — 2500

Div. 1: (500 — 500) — 1250 — 1250 — 2250 — 2250 — 2750

Мы надеемся, что вам понравится решать наши задачи!

Разбор

Поздравляем победителей!

Div. 2:

1. billieeyelash
2. randboy
3. TasselFlower
4. AVRush
5. Shiroqwq_

Div. 1:

1. tourist
2. maroonrk
3. Petr
4. ksun48
5. Radewoosh

Задача

Будем считать число плохих перестановок, в конце вычтем его из $$$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 есть доказательство проще.