Это сложная версия этой задачи. Разница между легкой и сложной версиями заключается в ограничении на \(k\) и ограничении по времени. Кроме того, в этой версии вам нужно вычислить ответ для всех положительных целых чисел \(n \in [1,k]\) в этой версии. Вы можете делать взломы только в том случае, если обе версии задачи решены.
Cirno играет в военный симулятор с \(n\) башнями (пронумерованными от \(1\) до \(n\)) и \(n\) ботами (пронумерованными от \(1\) до \(n\)). Первоначально \(i\)-я башня занята \(i\)-м ботом для всех \(1 \le i \le n\).
Перед игрой Cirno сначала выбирает перестановку \(p = [p_1, p_2, \ldots, p_n]\) длины \(n\) (перестановкой длины \(n\) называется массив длины \(n\), где каждое целое число между \(1\) и \(n\) встречаются ровно один раз). После этого она может выбрать последовательность \(a = [a_1, a_2, \ldots, a_n]\) (\(1 \le a_i \le n\) и \(a_i \ne i\) для всех \(1 \le i \le n\) ).
В игре есть \(n\) раундов-атак. В \(i\)-м раунде, если \(p_i\)-й бот все еще находится в игре, он начнет свою атаку, в результате чего \(a_{p_i}\)-я башня будет занята \(p_i\)-м ботом; бот, который ранее занимал \(a_{p_i}\)-ю башню, больше не будет ее занимать. Если \(p_i\)-го бота нет в игре, в этом раунде ничего не произойдет.
После каждого раунда, если бот не занимает ни одной башни, он будет уничтожен и покинет игру. Обратите внимание, что ни одна башня не может быть занята более чем одним ботом, но один бот может занимать более одной башни во время игры.
В конце игры Cirno запишет результат в виде последовательности \(b = [b_1, b_2, \ldots, b_n]\), где \(b_i\) — номер бота, занимающего \(i\)-ю башня в конце игры.
Однако, как мастер математики, она хочет, чтобы вы решили следующую задачу на счет вместо того, чтобы играть в игры:
Подсчитайте количество различных пар последовательностей \(a\) и \(b\), которые могут получиться при всех возможных выборах последовательности \(a\) и перестановки \(p\).
Вычислите ответ для всех значений \(n\) таких, что \(1 \le n \le k\). Так как эти числа могут быть большими, выведите их по модулю \(M\).
Примечание
Для \(n=1\) допустимой последовательности \(a\) не существует. Мы рассматриваем ответ как \(0\).
При \(n=2\) возможен только один массив \(a\): \([2, 1]\).
- Для массива \(a\) равного \([2, 1]\) и перестановки \(p\) равной \([1, 2]\), последовательность \(b\) будет \([1, 1]\) после всех раундов. Детали для каждого раунда:
- В первом раунде первый бот начнет атаку и успешно захватит башню \(2\). После этого раунда второй бот будет уничтожен и покинет игру, так как все его башни заняты другими ботами.
- Во втором раунде второго бота нет в игре.
- Для массива \(a\) равного \([2, 1]\) и перестановки \(p\) равной \([2, 1]\), последовательность \(b\) будет \([2, 2]\) после всех раундов. Детали для каждого раунда:
- В первом раунде второй бот начнет атаку и успешно захватит башню \(1\). После этого раунда первый бот будет уничтожен и покинет игру, так как все его башни заняты другими ботами.
- Во втором раунде первого бота нет в игре.
Таким образом, количество различных пар последовательностей \((a,b)\) равно \(2\) (\([2, 1]\), \([1, 1]\) и \([2, 1]\), \([2, 2]\)) при \(n=2\).