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.