問題一覧 > 通常問題

No.1504 Numeronym

レベル : / AI推定難易度 : 2100 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 35
作問者 : そすうぽよ / テスター : やむなく
お気に入りにしたユーザー ProblemId : 3708 / 自分の提出
問題文最終更新日: 2020-12-19 00:10:26
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. Back to the original
yukicoder contest 294 (順位表) の他の問題:

Problem Statement

A "numeronym" is an abbreviation of a string of $2$ or more characters using digits: only the first and last characters of the original string are kept, and the characters between them are replaced by the number of those characters.

For example, the string "internationalization" consists of "i" + ($18$ characters) + "n", so its numeronym is "i18n".
Note that the length excluding the first and last characters is used, not the length of the whole word.
Other examples: "animal" is converted to "a4l", "cat" to "c1t", and "we" to "w0e".
Numeronyms are not defined for strings of at most $1$ character (strings consisting of $1$ character, and the empty string).

You are given a string $S$ of length $N$ consisting only of "i" and "n".
There are $2^N$ ways to choose a not necessarily contiguous subsequence of $S$.
Among these, let $X_k$ be the number of ways to choose a subsequence of length $2$ or more whose numeronym is "i$k$n", modulo $998244353$.
Find the bitwise exclusive OR (xor) $X_0 \oplus X_1 \oplus \cdots \oplus X_{N-2}$ of $X_k$ over all $k = 0,1,2, ..., N-2$.
Here, two ways of choosing a subsequence are considered different if there exists some $i(1\leq i\leq N)$ such that the $i$-th character of the string $S$ is used in one subsequence but not in the other.
Note that subsequences that are identical as strings are counted separately if they are chosen differently.

Input

$N$
$S$

$2 \leq N \leq 300000$
$N$ is an integer.
$S$ is a string consisting only of "i" and "n".

Output

Output the answer in $1$ line.
Print a newline at the end.

Sample

Sample 1
Input
3
inn
Output
3

There are $8$ ways to choose a subsequence of "inn": (empty string), $S_1$, $S_2$, $S_3$, $S_1S_2$, $S_1S_3$, $S_2S_3$, $S_1S_2S_3$. As strings, they are "", "i", "n", "n", "in", "in", "nn", "inn", respectively. Among these, those whose numeronym is "i0n" are the $2$ ways $S_1S_2$ and $S_1S_3$, and the one whose numeronym is "i1n" is the $1$ way $S_1S_2S_3$. Therefore, the value to output is $3$, the exclusive OR of $1$ and $2$.

Sample 2
Input
6
ininin
Output
3

For example, the ways to choose a subsequence whose numeronym is "i2n" are the following $8$ ways: $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$. The numbers of ways to choose a subsequence whose numeronym is "i0n", "i1n", "i2n", "i3n", "i4n" are $6,8,8,4,1$, respectively, so output $6 \oplus 8 \oplus 8 \oplus 4 \oplus 1 = 3$.

Sample 3
Input
8
nnnnniii
Output
0

It may be impossible to choose a subsequence satisfying the condition.

Sample 4
Input
40
ininnninniiinnnninininininnnniininninnin
Output
74145471

Do not forget to output the exclusive OR of the remainders modulo $998244353$.

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