NOIP '20 P2 - String Matching - DMOJ: Modern Online Judge

NOIP '20 P2 - String Matching

Points: 12 (partial)

Time limit: 1.0s

Memory limit: 512M

Problem type

Little C has just finished learning about string matching, and he is practicing now.

For a string $S$ ~S~, the question asks him to find the number of ways to split $S$ ~S~ in the following form:

$S = ABC$ ~S = ABC~, $S = ABABC$ ~S = ABABC~, $S = ABAB \dots ABC$ ~S = ABAB \dots ABC~, where $A$ ~A~, $B$ ~B~, $C$ ~C~ are all non-empty strings. The number of characters appearing an odd number of times in $A$ ~A~ will not be more than the number of characters appearing an odd number of times in $C$ ~C~.

More specifically, we can define $AB$ ~AB~ to represent the concatenation of two strings $A$ ~A~ and $B$ ~B~. For example $A = \texttt{aab}$ ~A = \texttt{aab}~, $B = \texttt{ab}$ ~B = \texttt{ab}~, then $AB = \texttt{aabab}$ ~AB = \texttt{aabab}~.

We also recursively define $A^1 = A$ ~A^1 = A~, $A^n = A^{n-1} A$ ~A^n = A^{n-1} A~ ( $n \ge 2$ ~n \ge 2~ and is a positive integer). For example, $A = \texttt{abb}$ ~A = \texttt{abb}~, then $A^3 = \texttt{abbabbabb}$ ~A^3 = \texttt{abbabbabb}~.

Little C's problem is asking to find the number of ways of $S = (AB)^i C$ ~S = (AB)^i C~, where $F(A) \le F(C)$ ~F(A) \le F(C)~; $F(S)$ ~F(S)~ represents the number of characters that appear an odd number of times in $S$ ~S~. Two ways are considered different if and only if at least one string in the split $A$ ~A~, $B$ ~B~ and $C$ ~C~ is different.

Little C doesn't know how to solve this problem, so he asked you for help.

Input Specification

A positive integer $T$ ~T~ in the first line of the input file represents the number of data sets in the input.

The next $T$ ~T~ lines contain a string $S$ ~S~ for each data set on each line. $S$ ~S~ consisting of lowercase letters only.

Output Specification

For each data set, output a line with one integer indicating the answer.

Sample Input 1

3
nnrnnr
zzzaab
mmlmmlo

Sample Output 1

8
9
16

Explanation for Sample 1

All possible ways are

$A=\texttt{n}$ ~A=\texttt{n}~, $B=\texttt{nr}$ ~B=\texttt{nr}~, $C=\texttt{nnr}$ ~C=\texttt{nnr}~.
$A=\texttt{n}$ ~A=\texttt{n}~, $B=\texttt{nrn}$ ~B=\texttt{nrn}~, $C=\texttt{nr}$ ~C=\texttt{nr}~.
$A=\texttt{n}$ ~A=\texttt{n}~, $B=\texttt{nrnn}$ ~B=\texttt{nrnn}~, $C=\texttt{r}$ ~C=\texttt{r}~.
$A=\texttt{nn}$ ~A=\texttt{nn}~, $B=\texttt{r}$ ~B=\texttt{r}~, $C=\texttt{nnr}$ ~C=\texttt{nnr}~.
$A=\texttt{nn}$ ~A=\texttt{nn}~, $B=\texttt{rn}$ ~B=\texttt{rn}~, $C=\texttt{nr}$ ~C=\texttt{nr}~.
$A=\texttt{nn}$ ~A=\texttt{nn}~, $B=\texttt{rnn}$ ~B=\texttt{rnn}~, $C=\texttt{r}$ ~C=\texttt{r}~.
$A=\texttt{nnr}$ ~A=\texttt{nnr}~, $B=\texttt{n}$ ~B=\texttt{n}~, $C=\texttt{nr}$ ~C=\texttt{nr}~.
$A=\texttt{nnr}$ ~A=\texttt{nnr}~, $B=\texttt{nn}$ ~B=\texttt{nn}~, $C=\texttt{r}$ ~C=\texttt{r}~.

Sample Input 2

5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab

Sample Output 2

Additional Samples

Additional samples can be found here.

Sample 3 (string3.in and string3.ans).
Sample 4 (string4.in and string4.ans).

Constraints

Test Case	$\vert S \vert \le$ ~\vert S \vert \le~	Additional Constraints
$1 \sim 4$ ~1 \sim 4~	$10$ ~10~	None
$5 \sim 8$ ~5 \sim 8~	$100$ ~100~	None
$9 \sim 12$ ~9 \sim 12~	$1\,000$ ~1\,000~	None
$13 \sim 14$ ~13 \sim 14~	$2^{15}$ ~2^{15}~	$S$ ~S~ contains only one character
$15 \sim 17$ ~15 \sim 17~	$2^{16}$ ~2^{16}~	$S$ ~S~ contains only two characters
$18 \sim 21$ ~18 \sim 21~	$2^{17}$ ~2^{17}~	None
$22 \sim 25$ ~22 \sim 25~	$2^{20}$ ~2^{20}~	None

For all test cases, $1 \le T \le 5$ ~1 \le T \le 5~, $1 \le |S| \le 2^{20}$ ~1 \le |S| \le 2^{20}~.

Problem translated to English by Tommy_Shan.

Comments

There are no comments at the moment.