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

NOIP '20 P2 - String Matching

View as PDF

Submit solution

All submissions

Best submissions

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 = A B C$ , $S = ABABC$ $S = A B A B C$ , $S = ABAB \dots ABC$ $S = A B A B \dots A B C$ , 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$ $A B$ to represent the concatenation of two strings $A$ $A$ and $B$ $B$ . For example $A = \texttt{aab}$ $A = aab$ , $B = \texttt{ab}$ $B = ab$ , then $AB = \texttt{aabab}$ $A B = 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 \geq 2$ and is a positive integer). For example, $A = \texttt{abb}$ $A = abb$ , then $A^3 = \texttt{abbabbabb}$ $A^{3} = abbabbabb$ .

Little C's problem is asking to find the number of ways of $S = (AB)^i C$ $S = (A B)^{i} C$ , where $F(A) \le F(C)$ $F (A) \leq 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

Copy

3
nnrnnr
zzzaab
mmlmmlo

Sample Output 1

Copy

8
9
16

Explanation for Sample 1

All possible ways are

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

Sample Input 2

Copy

5
kkkkkkkkkkkkkkkkkkkk
lllllllllllllrrlllrr
cccccccccccccxcxxxcc
ccccccccccccccaababa
ggggggggggggggbaabab

Sample Output 2

Copy

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$ $\| S \| \leq$	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 \leq T \leq 5$ , $1 \le |S| \le 2^{20}$ $1 \leq | S | \leq 2^{20}$ .

Problem translated to English by Tommy_Shan.

Comments

There are no comments at the moment.