問題一覧 > 通常問題

No.1504 ヌメロニム

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 24
作問者 : そすうぽよそすうぽよ / テスター : やむなくやむなく
4 ProblemId : 3708 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2020-12-19 00:10:26

問題文

「ヌメロニム」とは、$2$ 文字以上の文字列を、数字を用いて省略した文字列で、元の文字列の先頭と末尾のみ残し、間にあった文字をその文字数で置き換えたものです。

例えば、"internationalization" という文字列は、"i" + ($18$ 文字) + "n" で構成されているので、ヌメロニムにすると "i18n" となります。
単語全体の長さではなく、先頭と末尾を除いた長さを用いることに注意してください。
他にも、"animal" は "a4l"、"cat" は "c1t"、"we" は "w0e"と変換されます。
$1$ 文字以下の文字列($1$ 文字からなる文字列と、空文字列)にはヌメロニムは定義されません。

"i" と "n" のみからなる長さ $N$ の文字列 $S$ が与えられます。
$S$ の連続とは限らない部分列のとり方は、 $2^N$ 通りあります。
このうち、部分列の長さが $2$ 以上であって、ヌメロニムが "i$k$n" になる部分列のとり方の個数を $998244353$ で割った余りを、$X_k$ とします。
すべての $k = 0,1,2, ..., N-2$ についての $X_k$ の排他的論理和(xor) $X_0 \oplus X_1 \oplus \cdots \oplus X_{N-2}$ を求めてください。
ただし、二つの部分列のとり方が異なるとは、ある $i(1\leq i\leq N)$ が存在して、文字列 $S$ の $i$ 文字目が、一方の部分列では使われているが、もう一方の部分列では使われていないことを指します。
文字列として同じ部分列であっても、とり方が違うものは個別に数えることに注意してください。

入力

$N$
$S$

$2 \leq N \leq 300000$
$N$ は整数
$S$ は "i" と "n" のみからなる文字列である。

出力

答えを $1$ 行で出力してください。
最後に改行してください。

サンプル

サンプル1
入力
3
inn
出力
3

"inn" の部分列のとり方には、(空文字列), $S_1$, $S_2$, $S_3$, $S_1S_2$, $S_1S_3$, $S_2S_3$, $S_1S_2S_3$ の $8$ 通りがあり、それぞれ文字列としては "", "i", "n", "n", "in", "in", "nn", "inn" であり、このうちヌメロニムが "i0n" になるものは $S_1S_2$ と $S_1S_3$ の $2$ 通り、"i1n" になるものは $S_1S_2S_3$ の $1$ 通りです。 したがって、出力すべき値は $1$ と $2$ の排他的論理和である $3$ になります。

サンプル2
入力
6
ininin
出力
3

例えば、ヌメロニムが "i2n" になる部分列のとり方は、$S_1S_2S_3S_4$, $S_1S_2S_3S_6$, $S_1S_2S_4S_6$, $S_1S_2S_5S_6$, $S_1S_3S_4S_6$, $S_1S_3S_5S_6$, $S_1S_4S_5S_6$, $S_3S_4S_5S_6$ の $8$ 通りです。 ヌメロニムが "i0n", "i1n", "i2n", "i3n", "i4n" となる部分列のとり方はそれぞれ $6,8,8,4,1$ 通りなので、$6 \oplus 8 \oplus 8 \oplus 4 \oplus 1 = 3$ を出力します。

サンプル3
入力
8
nnnnniii
出力
0

条件を満たす部分列が取れないこともあります。

サンプル4
入力
40
ininnninniiinnnninininininnnniininninnin
出力
74145471

$998244353$ で割った余りの排他的論理和を出力することを忘れないでください。

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