問題一覧 > 通常問題

No.2243 Coaching Schedule

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 46
作問者 : noya2noya2 / テスター : shobonvipshobonvip 👑 NachiaNachia
0 ProblemId : 9079 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2023-03-10 01:28:29

問題文

noya君は競プロでもっと強くなるためには分野 1,2,,M1,2,\dots ,MMM 個の苦手分野を克服する必要があると考えました。

noya君には競プロのエキスパートの友人が NN 人います。ii 番目の友人の得意分野は分野 AiA_i なので、 ii 番目の友人には分野 AiA_i を教えてもらう予定です。

noya君は今日から 11 日以上の集中精進期間を設け、その期間中は毎日 11 分野以上の苦手分野を選んで精進します。 選んだ分野 11 つにつきちょうど 11 人の友人にその分野を教わります。 ただし、友人は全員忙しいため、期間中ちょうど 11 日ずつ講師をお願いすることにします。

NN 人の友人のnoya君に教える日程の組み合わせとしてありえるものの個数を 998244353998244353 で割ったあまりを求めてください。

制約

  • 入力はすべて整数
  • 1M,N1051\le M, N\le 10^5
  • 1AiM (1iN)1\le A_i\le M\ (1\le i\le N)

入力

MM NN
A1A_1 A2A_2 \dots ANA_N

出力

NN 人の友人のnoya君に教える日程の組み合わせとしてありえるものの個数を 998244353998244353 で割ったあまりを求めてください。

サンプル

サンプル1
入力
2 3
1 2 1
出力
10

友人 1,2,31,2,3 にそれぞれ精進期間の d1,d2,d3d_1,d_2,d_3 日目に教わるとします。

ありえる (d1,d2,d3)(d_1,d_2,d_3) は次の 1010 通りです。

(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)(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

苦手な分野は 100100 個ありますが、友人の得意分野は分野 99 ばかりです。

998244353998244353 で割ったあまりを求めてください。

サンプル3
入力
10 13
2 7 1 8 2 8 1 8 2 8 4 5 9
出力
612761073

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。