Это сложная версия задачи. Отличие между версиями заключается в том, что в этой версии ограничения на \(t\), \(k\) и \(m\) выше. Вы можете делать взломы только в том случае, если решили все версии этой задачи.
Последовательность \(a\) из \(n\) целых чисел называется хорошей, если выполняется следующее условие:
- Пусть \(\text{cnt}_x\) — количество вхождений \(x\) в последовательность \(a\). Для всех пар \(0 \le i < j < m\), по крайней мере одно из следующих условий должно быть истинным: \(\text{cnt}_i = 0\), \(\text{cnt}_j = 0\) или \(\text{cnt}_i \le \text{cnt}_j\). Другими словами, если и \(i\), и \(j\) присутствуют в последовательности \(a\), то число вхождений \(i\) в \(a\) меньше или равно числу вхождений \(j\) в \(a\).
Вам даны целые числа \(n\) и \(m\). Вычислите значение побитового XOR медиан\(^{\text{∗}}\) всех хороших последовательностей \(a\) длины \(n\), таких, что \(0\le a_i < m\).
Обратите внимание, что значение \(n\) может быть очень большим, поэтому вместо него вам даётся его двоичное представление.
Примечание
В первом наборе входных данных, \(n = 10_2 = 2\) и \(m = 3\). Существуют такие последовательности с элементами меньше \(m\): \([0, 0]\), \([0, 1]\), \([0, 2]\), \([1, 0]\), \([1, 1]\), \([1, 2]\), \([2, 0]\), \([2, 1]\), \([2, 2]\). Все они являются хорошими, поэтому ответ равен \(0 \oplus 0 \oplus 0 \oplus 0 \oplus 1 \oplus 1 \oplus 0 \oplus 1 \oplus 2 = 3\).
Во втором наборе входных данных, \(n = 11_2 = 3\) и \(m = 3\). Некоторыми хорошими последовательностями являются \([2, 2, 2]\), \([1, 0, 1]\), и \([2, 0, 1]\). Однако последовательность \([2, 0, 0]\) не является хорошей, потому что \(\text{cnt}_0 = 2\), \(\text{cnt}_2 = 1\). Следовательно, если мы выберем \(i = 0\) и \(j = 2\), то \(i < j\) выполняется, а \(\text{cnt}_i \le \text{cnt}_j\) неверно.