問題一覧 > 通常問題

No.1766 Tatsujin Remix

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 51
作問者 : first_vilfirst_vil / テスター : nebocconebocco 👑 ygussanyygussany
2 ProblemId : 7150 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-11-26 14:44:59

問題文

ある文字列 $X$ が叩きやすいとは以下の条件を満たすことを言います。

  • $X_i=$ . を満たすすべての奇数 $i$ について、$X_{i-1},X_{i+1}$ はそれぞれ存在するならば . である。

なお、この問題における文字列のindexは $1$ から始まります。

またある文字列 $Y,Y^{\prime}$ について、$Y^{\prime}$ が $Y$ のアレンジであるとは以下の条件をすべて満たすことを言います。

  1. $|Y^{\prime}|=|Y|$
  2. $Y^{\prime}$ は .,d,k のみからなる
  3. $Y_i \neq$ . ならば $Y^{\prime}_i=Y_i$
  4. $Y_i=$ . かつ $Y_{i+1} \neq$ . ならば $Y^{\prime}_i \neq Y_{i+1}\ (i \lt |Y|)$

ここで .,d,k のみからなる長さ $16N$ の文字列 $S$ が与えられます。

$S$ のアレンジ $S^{\prime}$ のうち、叩きやすいものはいくつありますか? $998244353$ で割ったあまりを求めてください。

入力

$N$
$S_{1 \dots 16}$
$S_{17 \dots 32}$
$\vdots$
$S_{16N-15 \dots 16N}$
  • $N$ は $1$ 以上 $12500$ 以下の整数
  • $S$ は .,d,k のみからなる長さ $16N$ の文字列
  • $S$ は $16$ 文字ごとに改行区切りで与えられる

出力

$S$ のアレンジ $S^{\prime}$ のうち、叩きやすいものの個数を $998244353$ で割ったあまりを出力し、最後に改行してください。

サンプル

サンプル1
入力
4
ddddkkddd.d.kkdd
ddddkkddkkddkkdd
ddddkkddd.d.kkdd
ddddkkddkkddkkdd
出力
16

アレンジの条件 $2$ より ..,d,kのいずれかに変更されなければいけませんが、アレンジの条件 $4$ より元々直後にあったd,kと一致するような変更はできないため、このケースの . の変更先はそれぞれ $2$ 通りずつあることが分かります。よってそれらの組み合わせ $2^4=16$ 通りが答えとなります。$S$ 自身も $S$ のアレンジであることに注意してください。

サンプル2
入力
4
k..kk.k.kk..k..k
k.k.kk..k..kk.k.
kk..k..kk.k.kk..
k..kk.k.kk..k..k
出力
764411904
サンプル3
入力
6
.ddkdd.kddk.kdd.
kk..............
d.....kk......d.
ddk.......k.k...
.ddkdd.kddk.kdd.
dd....d.d.kkk...
出力
398264397
サンプル4
入力
8
d.....k.d...k.k.
d.dkd.kkd...d.k.
d...k...d.kkd.k.
d.d.k...k...d.k.
k...d.k.k...k.d.
k.kkd.k.d...k.d.
k...k.d.k.k.d.k.
d.kkd.k.d...d...
出力
228829591

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