No.3040 Aoiスコア
レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 92
作問者 :
Nauclhlt🪷
/ テスター :
Blue_S
eiram
naniwazu
タグ : / 解いたユーザー数 92
作問者 :


問題文最終更新日: 2025-02-28 21:45:51
ストーリー
eiramくんはあおいさんが大好きなので、aoi
の並びを見ると嬉しくなります。
問題文
各頂点に英小文字が書かれたある単純無向グラフ$H=(V_H, E_H)$に対して、このグラフのスコアを次のように定義します。
- $H$上の3頂点を通る単純パス$(v_1, e_1, v_2, e_2, v_3)$であって、次を満たすものの個数
- 頂点$v_1, v_2, v_3$に書かれている文字はそれぞれ
a
,o
,i
である
- 頂点$v_1, v_2, v_3$に書かれている文字はそれぞれ
$N$頂点$M$辺の単純無向グラフ$G$があります。$i(1\leq i\leq M)$番目の辺は頂点$A_i$と頂点$B_i$の間に張られた辺です。
また、英小文字と?
からなる長さ$N$の文字列$S$が与えられます。
$S$に含まれる?
の個数を$q$としたとき、$S$に含まれる?
を英小文字で置き換えてできる文字列$S'$として考えられるものは$26^q$個ありますが、そのすべてに対する次の値の総和を求めてください。
- $G$の各頂点$i(1\leq i\leq N)$に$S'_i$を書いてできるグラフのスコア($S'$の$i$文字目を$S'_i$で表す)
答えは非常に大きくなることがあるので$998244353$で割った余りを求めてください。
入力
$N\ M$ $S$ $A_1\ B_1$ $A_2\ B_2$ $\vdots$ $A_M\ B_M$
- $3\leq N\leq 6000$
- $0\leq M\leq \min(6000, \frac{N(N-1)}{2})$
- $S$は英小文字および
?
からなる長さ$N$の文字列 - $1\leq A_i\lt B_i\leq N$
- $G$は単純無向グラフ. つまり$i\neq j\Leftrightarrow (A_i, B_i)\neq (A_j, B_j)$かつ$A_i\neq B_i$
- 入力は$S$を除いてすべて整数
出力
求める総和を$998244353$で割った余りを$r$として次の形式で1行に出力してください。
$r$
最後に改行してください。
サンプル
サンプル1
入力
4 4 aoio 1 2 2 3 3 4 1 4
出力
2
$S$に?
が含まれないので、与えられた$S$に対してのみ考えればよいです。
条件を満たす単純パスは$1\rightarrow 2\rightarrow 3$と$1\rightarrow 4\rightarrow 3$の2つなので、2
を出力します。
サンプル2
入力
3 2 ??? 1 2 2 3
出力
2
$S'=$aoi
または$S'=$ioa
とした場合のみスコアが1となり、それ以外では0です。よって2
を出力します。
サンプル3
入力
5 4 ?ai?t 1 2 1 3 2 4 2 5
出力
26
頂点1にo
が書かれなければスコアは0です。頂点1にo
が書かれるとしたとき、頂点4に書く英小文字として26通りあるので、26
を出力します。
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。