問題一覧 > 通常問題

No.3040 Aoiスコア

レベル : / 実行時間制限 : 1ケース 1.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 92
作問者 : Nauclhlt🪷 / テスター : Blue_S eiram naniwazu
0 ProblemId : 11797 / 出題時の順位表 / 自分の提出
問題文最終更新日: 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である

$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もしくは右上の雲マークをクリックしてアカウントを作成してください。