No.2963 Mecha DESU
タグ : / 解いたユーザー数 59
作問者 :
twitteryou
/ テスター :
👑 Story
A feeble justice, drowning in a feeble festivalTo give the Don Rangers a stern rebuke
Now, here I have come
If you know no fear, come at me!
(Quoted from "Mecha Desu." from Taiko no Tatsujin Namco Original)
Ka〇-chan: "I won't give up the lead role, Don! Listen to my passionate performance, Do-n!!"
(Quoted from Taiko no Tatsujin 3DS "Chibi Dragon and the Mysterious Orb")
Problem Statement
There are currently $N$ zombies on a number line: for each $i=1,2,3,\cdots,N$, there is $1$ zombie at coordinate $i$.
You also have $M$ cards in your hand, and the integer written on the $i$-th card is $A_i$.
You will now repeat the following action $K$ times.
Each card is chosen with equal probability, and the card is returned to your hand after each action. Find the expected number of zombies that are electrocuted at least $1$ time during the $K$ operations, $\text{mod}$ $998244353$.
The answer can be expressed as an irreducible fraction $\frac{P}{Q}$ whose denominator is coprime to $998244353$, so find the $x(0 \leq x \leq 998244352)$ such that $Qx \equiv P$ $(\text{mod}$ $998244353)$.
Input
$N$ $M$ $K$ $A_1$ $A_2$ $\cdots$ $A_M$
Output
Output the expected number of electrocuted zombies.
Sample
Sample 1
Input
6 3 2 1 2 3
Output
110916044
The electrocuted zombies for each pair of drawn cards are as follows:
for $(1,1)$, zombies $1,2,3,4,5,6$;
for $(1,2)$, zombies $1,2,3,4,5,6$;
for $(1,3)$, zombies $1,2,3,4,5,6$;
for $(2,1)$, zombies $1,2,3,4,5,6$;
for $(2,2)$, zombies $2,4,6$;
for $(2,3)$, zombies $2,3,4,6$;
for $(3,1)$, zombies $1,2,3,4,5,6$;
for $(3,2)$, zombies $2,3,4,6$;
for $(3,3)$, zombies $3,6$.
Therefore, the expected number of electrocuted zombies is $\frac{43}{9}$.
Sample 2
Input
5 1 1 6
Output
0
It is possible that not even $1$ zombie is electrocuted.
Sample 3
Input
49 7 5 1 3 5 7 7 9 21
Output
375551832
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。