905 . 剪刀石頭布

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

omelet

User's AC Ratio

83.3% (5/6)

Submission's AC Ratio

28.6% (8/28)

Tags

ioicamp ioicamp-2025

Description

在 IOIC (International Olympiad of Initial Condition) 的最終決賽會場上，小 IO 跟小 IC 決定使用剪刀石頭布來決出勝負。但是一般的剪刀石頭布跟 Initial Condition 一點關係也沒有，為了讓比賽更加有趣，他們修改了一下遊戲規則。

一開始在世界上有三個陣營，分別代表剪刀，布，石頭，其中每個陣營分別有 $N_A, N_B, N_C$ 的士兵。接著電腦會均等隨機的選出兩個士兵並進行一場打架，這兩個士兵會出代表自己陣營的拳，而輸的人會更改自己的陣營成勝者的陣營，平局則不會有事情發生。這個操作會持續到這世界上只剩下一個陣營。此時唯一留下的陣營就是本局的贏家。

小 IO 跟小 IC 發現這樣的遊戲只跟初始狀態有關，因此他們感到很滿意，但是他們想要知道，在給定的初始狀態下，三個陣營的勝率分別是多少。請你輸出對於每個陣營他的勝率，方便起見，請將結果 $\text{mod } P$ 後輸出。

Input Format

輸入只有一行，有四個以空格隔開的整數 $N_A, N_B, N_C, P$，代表這筆詢問的三個陣營分別有 $N_A, N_B, N_C$ 人

  • $0 \leq N_A, N_B, N_C \leq 114$
  • $1 \leq N_A + N_B + N_C \leq 114$
  • $3 \leq P \leq 10^ 9$
  • $P$ 是質數

Output Format

輸出一行 $P_A, P_B, P_C$ 代表三個陣營的勝率，方便起見，請將所有數字都 $\text{ mod } P$ 後輸出。

可以證明這個機率可以被表示成最簡分數 $\frac{x}{y}$，此時輸出 $x \times y^ {-1} \text{ mod } P$，其中 $y^ {-1}$ 是一個在 $0$ 跟 $P-1$ 之間的整數，並且 $y \times y^ {-1} \equiv 1 \pmod{P}$。

保證在本題的輸入中，對於任何途中可能經過的狀態定義出的機率裡面，$y$ 不被 $P$ 整除。

Sample Input 1

1 1 1 998244353

Sample Output 1

332748118 332748118 332748118

Sample Input 2

0 1 2 998244353

Sample Output 2

0 1 0

Sample Input 3

1 1 2 241879871

Sample Output 3

49616384 124040960 68222528

Sample Input 4

20 10 10 635078881

Sample Output 4

592489968 283358340 394309455

Hints

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~3 範例測資 0
2 0~39 $N_A + N_B + N_C \leq 40$ 50
3 0~63 無額外限制 50

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 4000 1048576 65536 1 2 3
1 4000 1048576 65536 1 2 3
2 4000 1048576 65536 1 2 3
3 4000 1048576 65536 1 2 3
4 4000 1048576 65536 2 3
5 4000 1048576 65536 2 3
6 4000 1048576 65536 2 3
7 4000 1048576 65536 2 3
8 4000 1048576 65536 2 3
9 4000 1048576 65536 2 3
10 4000 1048576 65536 2 3
11 4000 1048576 65536 2 3
12 4000 1048576 65536 2 3
13 4000 1048576 65536 2 3
14 4000 1048576 65536 2 3
15 4000 1048576 65536 2 3
16 4000 1048576 65536 2 3
17 4000 1048576 65536 2 3
18 4000 1048576 65536 2 3
19 4000 1048576 65536 2 3
20 4000 1048576 65536 2 3
21 4000 1048576 65536 2 3
22 4000 1048576 65536 2 3
23 4000 1048576 65536 2 3
24 4000 1048576 65536 2 3
25 4000 1048576 65536 2 3
26 4000 1048576 65536 2 3
27 4000 1048576 65536 2 3
28 4000 1048576 65536 2 3
29 4000 1048576 65536 2 3
30 4000 1048576 65536 2 3
31 4000 1048576 65536 2 3
32 4000 1048576 65536 2 3
33 4000 1048576 65536 2 3
34 4000 1048576 65536 2 3
35 4000 1048576 65536 2 3
36 4000 1048576 65536 2 3
37 4000 1048576 65536 2 3
38 4000 1048576 65536 2 3
39 4000 1048576 65536 2 3
40 4000 1048576 65536 3
41 4000 1048576 65536 3
42 4000 1048576 65536 3
43 4000 1048576 65536 3
44 4000 1048576 65536 3
45 4000 1048576 65536 3
46 4000 1048576 65536 3
47 4000 1048576 65536 3
48 4000 1048576 65536 3
49 4000 1048576 65536 3
50 4000 1048576 65536 3
51 4000 1048576 65536 3
52 4000 1048576 65536 3
53 4000 1048576 65536 3
54 4000 1048576 65536 3
55 4000 1048576 65536 3
56 4000 1048576 65536 3
57 4000 1048576 65536 3
58 4000 1048576 65536 3
59 4000 1048576 65536 3
60 4000 1048576 65536 3
61 4000 1048576 65536 3
62 4000 1048576 65536 3
63 4000 1048576 65536 3
Submit
Back to Top