Нечестная тасовка
Первая версия перемешивания на одном старом игровом сервере была такой: для каждого места i = 1, 2, …, n выбрать место j равновероятно из всех n и поменять карты на местах i и j. Похоже на честную тасовку, но это не она: nn равновероятных цепочек выборов не делятся поровну между n! раскладами.
Насколько велик перекос? Вначале на месте k лежит карта k. Для каждого вопроса «a b» найдите вероятность того, что карта, лежавшая на месте a, после перемешивания окажется на месте b, и выведите её, умноженную на n: при честной тасовке это было бы ровно 1.
Вход
В первой строке n и число вопросов q (1 ≤ n ≤ 105, 1 ≤ q ≤ 5). Дальше q строк по два числа a и b (1 ≤ a, b ≤ n).
Выход
На каждый вопрос — n·P(a → b) с абсолютной или относительной погрешностью не больше 10−6.
Примеры
Пример 1
3 4 1 1 2 1 3 1 2 2
1.000000000 1.111111111 0.888888889 0.888888889
Пример 2
52 4 2 1 52 1 1 52 52 52
1.352226153 0.742913844 1.000000000 1.000000000
Ограничения
- Время · Python
- 4000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 10 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Перебирать все nn цепочек не нужно. Достаточно следить за одной картой: на каком месте она может оказаться после каждого шага и с какой вероятностью.
2Подсказка 2
Распишите один шаг k: что происходит с вероятностью «карта на месте k» и с вероятностью «карта на месте p ≠ k»? Первая после шага всегда одна и та же.
3Идея
Пусть d[p] — вероятность, что наша карта на месте p, и q = 1 − 1/n. Шаг k меняет место k со случайным местом. Карта с места k уходит в любое место, а на место k приходит любая карта, поэтому после шага d[k] = 1/n. Карта с места p ≠ k уходит на k с вероятностью 1/n, а с k на p приходит тоже с вероятностью 1/n: d[p] ← q·d[p] + d[k]/n. Так за n шагов по n мест получается O(n2) — много для 105. Но на вопрос нужно только d[b] в конце, а ему нужны только значения d[k] в моменты шагов k.
4Разбор
Обозначим sk — вероятность, что карта на месте k прямо перед шагом k (места с нуля). До шага k место k меняли только шаги j < k, каждый по правилу для p ≠ j, поэтому
$$s_k = [k = a]\,q^k + \sum_{j Сумму не нужно пересчитывать заново: это бегущий итог T, который на каждом шаге умножается на q и получает слагаемое sk. С местом b то же самое: на шаге b его вероятность становится 1/n, а на каждом следующем шаге k — q·d[b] + sk/n. Один проход по шагам — и ответ готов. Проверим на трёх картах. Цепочек 33 = 27, и карта 2 оказывается на первом месте в 10 из них, а должна в 9: n·P = 10/9 ≈ 1,111. Карта 3 — в 8 цепочках: 8/9. Карта 1 — ровно в 9: на первом шаге она уходит на случайное место, а дальше всё симметрично. В колоде из 52 карт вторая карта попадает наверх на 35 % чаще честного, а последняя — на 26 % реже. Вся матрица таких вероятностей — во второй сцене статьи о тасовке. Две карты — особый случай: обмен «с любым» на двух местах честен, 22 = 4 цепочки делятся на 2! = 2 расклада поровну. С трёх карт начинается перекос: n − 1 делит n!, но не имеет общих делителей с nn.
4+Решение
5Сложность
O(n) времени на вопрос и O(1) памяти: один проход по шагам с двумя бегущими числами.
6Типичные ошибки
- Считать тасовку честной. Ответ 1 на всё — неверен уже в первом примере.
- Моделировать. Миллион случайных тасовок даст ответ с ошибкой около 10−3, а нужна 10−6: для этого понадобился бы триллион тасовок.
- Вся матрица. Вероятности всех карт на всех местах — O(n2) на одну карту и O(n3) на все. Для одного вопроса нужна одна карта и одно место.
- Перепутать порядок. Место b получает 1/n на своём шаге и меняется только на следующих; шаги до b на ответ влияют лишь через sk.
Алгоритмы задачи
O(n)
2 задачи
DP
Приём
Динамическое программирование
Сводим задачу к подзадачам, решаем каждую один раз и храним ответы в таблице.
состояния × переходы
2 задачи