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