Игра в ашыки


Отправить решение Решать в редакторе

Сложность: 85%
Очки: 100 (частичный балл)
Ограничение по времени: 2.0s
Ограничение по памяти: 256M

Автор:
Типы задач
Разрешённые языки
C, C#, C++, F#, Go, Java, JavaScript, Kotlin, Pascal, Python, Scratch

Айбек и Бекзат играют в ашыки (альчики). У Айбека a ашыков, у Бекзата — b. В каждом раунде Айбек выигрывает с вероятностью x / y и забирает один ашык у Бекзата, иначе Бекзат забирает один ашык у Айбека. Игра заканчивается, когда у кого-то из мальчиков не остаётся ни одного ашыка.

Рисунок

Найдите математическое ожидание числа раундов игры. Ответ — рациональное число P / Q; выведите P · Q⁻¹ по модулю 998244353.

Входные данные

В первой строке — число T (1 ≤ T ≤ 10⁵) — количество партий. В каждой из следующих T строк — четыре целых числа a b x y (1 ≤ a, b ≤ 10¹⁸, 1 ≤ x < y ≤ 10⁹).

Если 2x ≠ y, гарантируется, что число x^(a+b) − (y − x)^(a+b) не делится на 998244353.

Выходные данные

Для каждой партии выведите ожидаемое число раундов по модулю 998244353.

Пример 1

Вход:

3
1 1 1 3
2 3 1 2
1 2 2 3

Выход:

1
6
855638019

Пояснение

В первой партии у каждого по одному ашыку — игра длится ровно один раунд. Во второй шансы равны, и ожидание равно a · b = 6. В третьей у Айбека 1 ашык, у Бекзата 2, Айбек выигрывает раунд с вероятностью 2/3: ожидание равно 15/7.

Система оценивания

Решение проверяется на 20 тестах, каждый стоит 5 баллов. В 15 % тестов a + b ≤ 15, ещё в 10 % тестов a, b ≤ 10⁹.


Комментарии

Еще нет ни одного комментария.