Это усложненная версия задачи. Две версии отличаются ограничением на число мудрецов и ограничением по времени. Вы можете взламывать по этой задаче только если обе версии решены.
\(n\) мудрецов живут в красивом городе. Некоторые из них знают друг друга.
Для всех возможных \(n!\) перестановок \(p_1, p_2, \ldots, p_n\) мудрецов, построим бинарную строку длины \(n-1\): для всех \(1 \leq i < n\) положим \(s_i=1\) если мудрецы \(p_i\) и \(p_{i+1}\) знают друг друга, и \(s_i=0\) иначе.
Для всех \(2^{n-1}\) возможных бинарных строк, найдите число перестановок, при которых получается такая бинарная строка.
Выходные данные
Выведите \(2^{n-1}\) целых чисел, разделенных пробелами. Для каждого \(0 \leq x < 2^{n-1}\):
- Рассмотрим такую строку \(s\) длины \(n-1\), что \(s_i = \lfloor \frac{x}{2^{i-1}} \rfloor \bmod 2\) для \(1 \leq i \leq n - 1\).
- \((x+1)\)-е число должно быть необходимому ответу для \(s\).
Примечание
В первом тесте все мудрецы знакомы, соответственно для всех перестановок получается строка \(11\).
Во втором тесте
- Если \(p = \{1, 2, 3, 4\}\), строка будет равна \(101\), потому что мудрецы \(1\) и \(2\) знакомы, \(2\) и \(3\) не знакомы, \(3\) и \(4\) знакомы;
- Если \(p = \{4, 1, 2, 3\}\), строка будет равна \(110\), потому что мудрецы \(1\) и \(4\) не знакомы, \(1\) и \(2\) не знакомы, \(2\) и \(3\) не знакомы;
- Если \(p = \{1, 3, 2, 4\}\), строка будет равна \(000\), потому что мудрецы \(1\) и \(3\) не знакомы, \(3\) и \(2\) не знакомы, \(2\) и \(4\) не знакомы.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
011
101
110
|
0 0 0 6
|
|
2
|
4
0101
1000
0001
1010
|
2 2 6 2 2 6 2 2
|