Universal Cup Judging System

Universal Cup

حد الوقت: 2.0 s حد الذاكرة: 1024 MB مجموع النقاط: 100 قابلة للهجوم ✓
الإحصائيات

Имеется $U + T + P + C$ карт. Среди них на $U$ картах на лицевой стороне изображён единорог, на $T$ картах — тигр, на $P$ картах — панда, а на $C$ картах — кошка. Изначально все карты лежат рубашкой вверх, и невозможно определить, какая картинка находится на каждой из карт.

Вы будете играть в игру с этими картами. Игра состоит из нескольких ходов. На каждом ходу вы выбираете, выполнить ли Операцию A или Операцию B:

  • Операция A: Равновероятно случайно выберите одну из лежащих рубашкой вверх карт и переверните её лицевой стороной вверх. Если на открытой карте изображён единорог, тигр или панда, вы переходите к следующему ходу, и игра продолжается. Перевёрнутая карта остаётся лежать лицевой стороной вверх. Если на открытой карте изображена кошка, игра немедленно заканчивается. В этом случае ваш счёт будет равен $0$.
  • Операция B: Немедленно закончить игру. Пусть $u$ — количество открытых карт с изображением единорога, а $t$ — количество открытых карт с изображением тигра. Ваш счёт будет равен $2u + t$.

Найдите математическое ожидание счёта при следовании оптимальной стратегии, максимизирующей математическое ожидание счёта, по модулю $998244353$.

Примечание о математическом ожидании по модулю $998244353$

Можно доказать, что математическое ожидание в этой задаче всегда является рациональным числом. Кроме того, при ограничениях данной задачи, когда математическое ожидание представлено в виде несократимой дроби $\frac{x}{y}$, гарантируется, что $y$ не делится на $998244353$. Следовательно, существует единственное целое число $z$ ($0 \le z < 998244353$), такое что $y \cdot z \equiv x \pmod{998244353}$. Вам следует вывести это число $z$.

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

Входные данные подаются из стандартного потока ввода в следующем формате:

$$U \quad T \quad P \quad C$$

  • Все входные значения являются целыми числами.
  • $1 \le U, T, P, C \le 10^6$

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

Выведите ответ в единственной строке.

Примеры

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

1 1 1 1

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

166374060

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

2 7 1 8

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

300941313

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

20 26 2 14

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

631490021

Примечание

  • В первом примере возможен следующий ход игры (обратите внимание, что это не обязательно оптимальная стратегия):
    • Если на $1$-м ходу вы выполните Операцию B, ваш счёт будет равен $0$, и игра закончится. Предположим, вместо этого вы выполняете Операцию A, и на перевёрнутой карте оказывается единорог.
    • В этом состоянии, если на $2$-м ходу вы выполните Операцию B, ваш счёт будет равен $2$, и игра закончится. Предположим, вместо этого вы выполняете Операцию A, и на перевёрнутой карте оказывается панда.
    • В этом состоянии, если на $3$-м ходу вы выполните Операцию B, ваш счёт будет равен $2$, и игра закончится. Предположим, вместо этого вы выполняете Операцию A, и на перевёрнутой карте оказывается кошка. Поскольку была вытянута кошка, ваш счёт становится равным $0$, и игра заканчивается.
  • Если следовать оптимальной стратегии, можно показать, что математическое ожидание счёта равно $\frac{7}{6}$.

Editorials

IDTypeStatusTitlePosted ByLast UpdatedActions
#1415EditorialOpen题解jianglyView

Discussions

About Discussions

The discussion section is only for posting: General Discussions (problem-solving strategies, alternative approaches), and Off-topic conversations.

This is NOT for reporting issues! If you want to report bugs or errors, please use the Issues section below.

Open Discussions 0
No discussions in this category.

Issues

About Issues

If you find any issues with the problem (statement, scoring, time/memory limits, test cases, etc.), you may submit an issue here. A problem moderator will review your issue.

Guidelines:

  1. This is not a place to publish discussions, editorials, or requests to debug your code. Issues are only visible to you and problem moderators.
  2. Do not submit duplicated issues.
  3. Issues must be filed in English or Chinese only.
Active Issues 0
No issues in this category.
Closed/Resolved Issues 0
No issues in this category.