No.2243 Coaching Schedule
タグ : / 解いたユーザー数 46
作問者 :
noya2
/ テスター :
shobonvip
👑 
Nachia
問題文
noya君は競プロでもっと強くなるためには分野 $1,2,\dots ,M$ の $M$ 個の苦手分野を克服する必要があると考えました。
noya君には競プロのエキスパートの友人が $N$ 人います。$i$ 番目の友人の得意分野は分野 $A_i$ なので、 $i$ 番目の友人には分野 $A_i$ を教えてもらう予定です。
noya君は今日から $1$ 日以上の集中精進期間を設け、その期間中は毎日 $1$ 分野以上の苦手分野を選んで精進します。 選んだ分野 $1$ つにつきちょうど $1$ 人の友人にその分野を教わります。 ただし、友人は全員忙しいため、期間中ちょうど $1$ 日ずつ講師をお願いすることにします。
$N$ 人の友人のnoya君に教える日程の組み合わせとしてありえるものの個数を $998244353$ で割ったあまりを求めてください。
制約
- 入力はすべて整数
- $1\le M, N\le 10^5$
- $1\le A_i\le M\ (1\le i\le N)$
入力
$M$ $N$ $A_1$ $A_2$ $\dots$ $A_N$
出力
$N$ 人の友人のnoya君に教える日程の組み合わせとしてありえるものの個数を $998244353$ で割ったあまりを求めてください。
サンプル
サンプル1
入力
2 3 1 2 1
出力
10
友人 $1,2,3$ にそれぞれ精進期間の $d_1,d_2,d_3$ 日目に教わるとします。
ありえる $(d_1,d_2,d_3)$ は次の $10$ 通りです。
$(1,2,3),(1,3,2),(2,1,3),(2,3,1),(3,1,2),(3,2,1),(1,1,2),(1,2,2),(2,1,1),(2,2,1)$
サンプル2
入力
100 13 9 9 9 9 9 9 9 9 9 9 9 9 9
出力
237554682
苦手な分野は $100$ 個ありますが、友人の得意分野は分野 $9$ ばかりです。
$998244353$ で割ったあまりを求めてください。
サンプル3
入力
10 13 2 7 1 8 2 8 1 8 2 8 4 5 9
出力
612761073
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。