問題一覧 > 通常問題

No.2243 Coaching Schedule

レベル : / AI推定難易度 : 2300 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 47
作問者 : noya2 / テスター : shobonvip 👑 Nachia
お気に入りにしたユーザー ProblemId : 9079 / 自分の提出
問題文最終更新日: 2023-03-10 01:28:29
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 380 (順位表) の他の問題:

Problem Statement

Noya thinks that to get stronger at competitive programming, he needs to overcome his $M$ weak areas, areas $1,2,\dots ,M$.

Noya has $N$ friends who are competitive programming experts. The specialty of the $i$-th friend is area $A_i$, so the $i$-th friend is going to teach him area $A_i$.

Starting today, Noya will hold an intensive training period lasting $1$ or more days, and on each day of the period he chooses $1$ or more of his weak areas and trains in them. For every $1$ area he chooses, he is taught that area by exactly $1$ friend. However, since all the friends are busy, he will ask each of them to serve as a teacher on exactly $1$ day during the period.

Find the number of possible combinations of schedules on which the $N$ friends teach Noya, modulo $998244353$.

Constraints

  • All inputs are integers
  • $1\le M, N\le 10^5$
  • $1\le A_i\le M\ (1\le i\le N)$

Input

$M$ $N$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Find the number of possible combinations of schedules on which the $N$ friends teach Noya, modulo $998244353$.

Sample

Sample 1
Input
2 3
1 2 1
Output
10

Suppose that friends $1,2,3$ teach him on days $d_1,d_2,d_3$ of the training period, respectively.

The possible $(d_1,d_2,d_3)$ are the following $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)$

Sample 2
Input
100 13
9 9 9 9 9 9 9 9 9 9 9 9 9
Output
237554682

There are $100$ weak areas, but the friends' specialties are all area $9$.

Find the answer modulo $998244353$.

Sample 3
Input
10 13
2 7 1 8 2 8 1 8 2 8 4 5 9
Output
612761073

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