Відлуння перестановки#13045
Увійти

Відлуння перестановки (Розбір)

Розв'язання

Нехай

m=n+1.

Визначимо

P_i=p_1p_2\dots p_i \pmod m,

а також

P_0=1.

На позиції потрібно вибрати ще не використане значення p_i, для якого

P_{i-1}p_i\equiv b_i\pmod m.

Нехай

g=\gcd(P_{i-1},m).

Порівняння

P_{i-1}x\equiv b_i\pmod m

має розв'язок тоді і тільки тоді, коли

g\mid b_i.

Якщо ця умова не виконується, допустимої перестановки не існує.

Інакше позначимо

M=\frac{m}{g}.

Поділивши порівняння на , отримаємо

\frac{P_{i-1}}{g}p_i \equiv \frac{b_i}{g} \pmod M.

При цьому

\gcd\left(\frac{P_{i-1}}{g},M\right)=1.

Тому число \frac{P_{i-1}}{g} має обернений елемент за модулем .

Отже, p_i повинен належати рівно одному класу лишків:

p_i\equiv r\pmod M,

де

r= \frac{b_i}{g} \left(\frac{P_{i-1}}{g}\right)^{-1} \pmod M.

Таким чином, на кожному кроці потрібно лише знайти невикористане число з певного класу лишків за модулем .

Чому можна брати будь-якого представника

Нехай

x\equiv y\pmod M.

Оскільки

P_{i-1}=gq

та

m=gM,

маємо

P_{i-1}x-P_{i-1}y = gq(x-y).

Оскільки M\mid x-y, отримуємо

m\mid P_{i-1}x-P_{i-1}y.

Тому

P_{i-1}x\equiv P_{i-1}y\pmod m.

Отже, кожне число з потрібного класу лишків дає абсолютно однакове значення наступного префіксного добутку.

Тепер визначимо

g_i=\gcd(P_i,m)

та

M_i=\frac{m}{g_i}.

Оскільки

P_i=P_{i-1}p_i\pmod m,

виконується

g_{i-1}\mid g_i.

Отже,

M_i\mid M_{i-1}.

Тобто кожен наступний модуль ділить попередній.

Тому якщо два числа рівні за поточним модулем , то вони залишатимуться рівними і за всіма наступними модулями.

Таким чином, усі невикористані представники поточного класу лишків повністю еквівалентні, тому можна вибрати будь-який з них.

Підтримка невикористаних значень

Кожне можливе значення є дільником .

Для кожного дільника згрупуємо числа 1,2,\dots,n за їхнім лишком за модулем .

Для кожного класу лишків будемо зберігати вказівник на перше число, яке ми ще не перевіряли.

Коли нам потрібен певний клас лишків, рухаємо цей вказівник, доки поточне число вже використане.

Якщо невикористаних чисел у цьому класі більше немає, то продовжити побудову неможливо.

Інакше вибираємо знайдене число як p_i та позначаємо його використаним.

Після цього оновлюємо

P_i=P_{i-1}p_i\pmod m.

Доведення коректності

На кожному кроці умова на p_i еквівалентна належності до рівно одного класу лишків за модулем .

Кожне число з цього класу дає потрібний наступний префіксний добуток.

Оскільки кожен наступний модуль ділить поточний, усі представники поточного класу лишків залишатимуться еквівалентними й на всіх наступних кроках.

Тому вибір будь-якого невикористаного представника завжди безпечний.

Якщо невикористаного представника немає, то жодне невикористане число не може задовольнити поточне порівняння.

Отже, алгоритм будує допустиму перестановку тоді і тільки тоді, коли вона існує.

Складність

Нехай — кількість дільників числа .

Для кожного дільника кожне значення може бути оброблене лише сталу кількість разів.

Тому загальна складність становить

O(n\tau(m))

за часом та

O(n\tau(m))

за пам'яттю.