Universal Cup Judging System

Universal Cup

Time Limit: 2.0 s Memory Limit: 1024 MB Total points: 100 Hackable ✓
Statistics

有 $U + T + P + C$ 張卡牌。其中,$U$ 張正面畫有獨角獸(unicorn),$T$ 張畫有老虎(tiger),$P$ 張畫有貓熊(panda),$C$ 張畫有貓(cat)。初始時,所有卡牌都背面朝下放置,且無法區分每張卡牌正面畫的是什麼。

你將使用這些卡牌玩一個遊戲。遊戲由若干輪組成。在每一輪中,你選擇執行操作 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.