K - TUAT String 4
問題文
※本問題文中に登場する東京農工大学は、実在する東京農工大学との関係はありません。
東京農工大学では独自の言語を用いています。この言語は $M$ 種類の文字を持ち、それぞれの文字には $1, \dots, M$ の文字コードが割り当てられています。
長さ $N$ の文字列 $S$ を、各文字を文字コードに変換した数列 $C = (C_1, \dots, C_N)$ が与えられます。$S$ の $i$ 文字目の文字コードは $C_i$ です。
$S$ の $i$ 文字目を $S_i$ と表します。また、$f(S)$ を次の条件をすべて満たす整数 $(i, j, k, l)$ の組の個数と定義します。
- $1 \le i < j < k < l \le N$
- $S_i = S_l$
- $S_i \ne S_j$
- $S_i \ne S_k$
- $S_j \ne S_k$
$f(S)$ の値を $998244353$ で割った余りを求めてください。
制約
Hard (125点)
- $4 \le N \le 2 \times 10^5$
- $3 \le M \le 300$
- $1 \le C_i \le M$
- 入力される値はすべて整数
Normal (100点)
- Hard の制約に以下の制約を追加
- $M = 26$
Easy (75点)
- Hard の制約に以下の制約を追加
- $4 \le N \le 50$
- $M = 26$
部分点のみ解答したい場合
部分点のみを解答したい場合、問題によっては結果が TLE となるケースが大量に発生し、ジャッジに時間がかかる可能性があります。
C++の assert 関数やPythonの assert 文などを用いて、変数の値によってプログラムを強制終了させる処理を書き加えることで TLE を防ぎ、より早く結果を得ることができます。
入力
入力は以下の形式で標準入力から与えられます。
$N \ \ M$
$C_1 \ \ \dots \ \ C_N$
出力
答えを $1$ 行に出力してください。
9 26
16 18 15 3 5 19 19 15 18
18
以降の入出力例では、説明のため文字コードが $c$ の文字に $c$ 番目の英小文字を割り当てます。
$S =$ processor です。次にいくつか例を示します。
- $(i, j, k, l) = (2, 4, 6, 9)$ は条件を満たします。
- $S_2 =$
r$, S_4 =$c$, S_6 =$s$, S_9 =$rであり、条件をすべて満たすことが分かります。
- $S_2 =$
- $(i, j, k, l) = (2, 6, 7, 9)$ は条件を満たしません。
- $S_2 =$
r$, S_6 =$s$, S_7 =$s$, S_9 =$rであり、$S_j \ne S_k$ を満たさないことが分かります。
- $S_2 =$
$1 \le i < j < k < l \le N$ を満たす $(i, j, k, l)$ の組としては $210$ 通りありますが、このうち条件を満たす組は $18$ 通りあります。
したがって、$f(S) = 18$ より、$18$ を出力してください。
この入力例は Easy・Normal・Hard の制約を満たします。
4 26
20 21 1 20
1
$S =$ tuat です。
$1 \le i < j < k < l \le N$ を満たす唯一の組 $(i, j, k, l) = (1, 2, 3, 4)$ が条件を満たします。
したがって、$f(S) = 1$ より、$1$ を出力してください。
この入力例は Easy・Normal・Hard の制約を満たします。
11 26
13 9 19 19 9 19 19 9 16 16 9
12
$S =$ mississippi です。
選んだ $4$ 文字が文字としては同一でも、選んだ位置が異なる場合は区別することに注意してください。
例えば、$(i, j, k, l) = (2, 3, 9, 11), (5, 7, 10, 11)$ はいずれも $S_i =$ i $, S_j =$ s $, S_k =$ p $, S_l =$ i となりますが、これらは区別して数えます。
この入力例は Easy・Normal・Hard の制約を満たします。