Посчитать количество написать все $$$n!$$$ перестановок в одну строку, так, чтобы любые два соседних элемента были различны.
Я совершенно без понятия, как к этому подступиться.
Это может быть очевидно переформулированно в нечто более общее: у нас есть по $$$k$$$ (в конкретной задаче $$$(n-2)!$$$) пар $$$(i, j), i\neq j$$$. Расставить их в одну линию так, чтобы любые два соседних были различны.
Было бы очень круто узнать что угодно быстрее $$$O(n*2^{n!})$$$
"I am really stuck without any ideas."
Maybe you should tfr
каждую пару (i, j) можно как вершину графа интерпретировать, а так же у тебя ребра известны (i, j) -> (k != j, r). Тогда у тебя просто задача о количестве гамильтоновых путей в таком графе. Вершин n!, значит общее решение способно за n! * 2^(n!). Так что уже удивляет, как ты n*2^n! добился. Поделись, пожалуйста, как ты так.
еще была идея поддерживать cnt(i, j) — кол-во подстрок (i, j) в уже расставленном. Тогда легко обработать вставку (ik, jk) между (i, j) => cnt(i, j)--, cnt(i, ik)++, cnt(jk, j)++. Мб это можно раскрутить.
еще формулой включения-исключения можно попробовать. Скажем у нас есть cnt(k) — количество расстановок пар, таких что на k встречается повтор первый. Тогда это |pair|! — sum(cnt(k), k = 2..|pair|). Как это считать мне не ясно. Лишь просится dp, но тут видимо вылезут опять подмножества и это не сильно лучше 2^(n!)
Да уж, я действительно ошибся с асимптотикой.
Про гамильтоновы пути я думал, но так как там почти всё сразу np-полное, как-то сразу отмёл.
Спасибо за идеи!