Следующее число
Генератор хранит 48-битное число x. Чтобы выдать очередное число, он делает шаг x ← (25214903917·x + 11) mod 248 и выдаёт старшие 32 бита нового x, то есть ⌊x / 216⌋. Так устроен java.util.Random: младшие 16 бит состояния наружу не выходят.
Вы видели два числа, которые генератор выдал подряд. Выведите k чисел, которые он выдаст следом.
Вход
В первой строке — число генераторов T (1 ≤ T ≤ 10). Дальше T строк «o1 o2 k»: два числа подряд (0 ≤ o1, o2 < 232) и сколько следующих нужно (1 ≤ k ≤ 20). Гарантируется, что состояние генератора по двум числам восстанавливается однозначно.
Выход
Для каждого генератора — строку из k чисел через пробел.
Первый пример — тот же, что в листинге статьи.
Примеры
Пример 1
1 3462021164 1173812125 5
525041693 1392299345 2581698045 466075430 711990521
Пример 2
2 779501271 4044624960 3 4006504144 1178679997 4
2339400583 682989805 4045972280 3679756190 2684249300 754095740 2348544248
Ограничения
- Время · Python
- 3000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 7 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Сколько бит состояния неизвестно, когда видно первое число? Сколько вариантов это даёт и как проверить каждый?
2Идея
Первое число — старшие 32 бита состояния x1, после которого оно выдано. Неизвестны только младшие 16 бит: 65 536 вариантов. Для каждого делаем один шаг генератора и сравниваем старшие 32 бита со вторым числом. Неподходящий вариант совпадает случайно с вероятностью около 2−32, поэтому подходит, как правило, ровно один — условие это гарантирует. Найдя x1, просто запускаем генератор дальше: он детерминирован, и всё, что он выдаст, известно.
3Разбор
Для каждого генератора перебираем x от o1·216 до o1·216 + 216 − 1, пока ⌊((25214903917·x + 11) mod 248) / 216⌋ не станет равным o2. Затем делаем шаг до второго состояния и ещё k шагов, выводя старшие 32 бита.
В Go произведение не помещается в 64 бита, но это не мешает: умножение по модулю 264 и маска на младшие 48 бит дают то же, что умножение по модулю 248, потому что 248 делит 264.
3+Решение
4Сложность
Не больше 216 шагов генератора на каждый из T генераторов и ещё k шагов: O(T·(216 + k)).
5Типичные ошибки
- Считать младшие биты нулями. Тогда первое же предсказание расходится с настоящим: ошибка в младших битах после умножения уходит в старшие.
- Начинать с не того состояния. Найденное x1 выдало первое число; следующие k чисел идут после второго, то есть с третьего шага.
- Не те 32 бита. Наружу выходят старшие биты, x / 216, а не x mod 232; с младшими ни один вариант не совпадёт со вторым числом.