問題一覧 > 通常問題

No.1766 Tatsujin Remix

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : （解説公開後に AC するまで非表示） / 解いたユーザー数 59
作問者 : first_vil / テスター : ygussany nebocco
お気に入りにしたユーザー ProblemId : 7150 / 自分の提出
問題文最終更新日: 2021-11-26 14:44:59
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. Show the original
yukicoder contest 325 (順位表) の他の問題:

Problem Statement

A string $X$ is said to be easy to hit if it satisfies the following condition.

  • For every odd $i$ with $X_i=$ ., each of $X_{i-1},X_{i+1}$ is . if it exists.

Note that string indices in this problem start from $1$.

For strings $Y,Y^{\prime}$, $Y^{\prime}$ is said to be an arrangement of $Y$ if all of the following conditions are satisfied.

  1. $|Y^{\prime}|=|Y|$
  2. $Y^{\prime}$ consists only of .,d,k
  3. If $Y_i \neq$ ., then $Y^{\prime}_i=Y_i$
  4. If $Y_i=$ . and $Y_{i+1} \neq$ ., then $Y^{\prime}_i \neq Y_{i+1}\ (i \lt |Y|)$

You are given a string $S$ of length $16N$ consisting only of .,d,k.

How many arrangements $S^{\prime}$ of $S$ are easy to hit? Find the count modulo $998244353$.

Input

$N$
$S_{1 \dots 16}$
$S_{17 \dots 32}$
$\vdots$
$S_{16N-15 \dots 16N}$
  • $N$ is an integer between $1$ and $12500$, inclusive
  • $S$ is a string of length $16N$ consisting only of .,d,k
  • $S$ is given with a line break after every $16$ characters

Output

Output the number of arrangements $S^{\prime}$ of $S$ that are easy to hit, modulo $998244353$, followed by a newline.

Sample

Sample 1
Input
4
ddddkkddd.d.kkdd
ddddkkddkkddkkdd
ddddkkddd.d.kkdd
ddddkkddkkddkkdd
Output
16

By condition $2$ of arrangement, each . must be changed to one of .,d,k, but by condition $4$ of arrangement, it cannot be changed to the same character as the d or k originally right after it, so each . in this case has $2$ options. Therefore, the answer is the number of their combinations, $2^4=16$. Note that $S$ itself is also an arrangement of $S$.

Sample 2
Input
4
k..kk.k.kk..k..k
k.k.kk..k..kk.k.
kk..k..kk.k.kk..
k..kk.k.kk..k..k
Output
764411904
Sample 3
Input
6
.ddkdd.kddk.kdd.
kk..............
d.....kk......d.
ddk.......k.k...
.ddkdd.kddk.kdd.
dd....d.d.kkk...
Output
398264397
Sample 4
Input
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...
Output
228829591

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