NOI '16 P1 - Good Partitions - Olympiads Online Judge

NOI '16 P1 - Good Partitions

View as PDF

Submit solution

All submissions

Best submissions

Points: 20 (partial)

Time limit: 1.5s

Memory limit: 512M

Problem type

If a string can be written in the form of $\texttt{AABB}$ $AABB$ where $\texttt{A}$ $A$ and $\texttt{B}$ $B$ are arbitrary non-empty strings, then we say this is a good partition. For example, it is possible to write the string $\texttt{aabaabaa}$ $aabaabaa$ in the form of $\texttt{AABB}$ $AABB$ by letting $\texttt{A} = \texttt{aab}$ $A = aab$ and $\texttt{B} = \texttt{a}$ $B = a$ .

Some strings do not admit a good partition, while some strings admit multiple good partitions. For example, for the above string $\texttt{aabaabaa}$ $aabaabaa$ , it is also possible to write it in the form of $\texttt{AABB}$ $AABB$ by letting $\texttt{A} = a$ $A = a$ and $\texttt{B} = \texttt{baa}$ $B = baa$ . The string $\texttt{abaabaa}$ $abaabaa$ does not admit good partitions.

Given a string $S$ $S$ of length $n$ $n$ , compute the sum, over all its substrings, of the number of good partitions of those substrings. Here, substring refers to a contiguous part of the string.

Please pay attention to the following details:

The same string appearing at different locations are considered distinct. All good partitions corresponding to the same string should count towards the answer.
It is possible to have $\texttt{A} = \texttt{B}$ $A = B$ in a good partition. For example, the string $\texttt{cccc}$ $cccc$ admits good partition $\texttt{A} = \texttt{B} = \texttt{c}$ $A = B = c$ .
The string $S$ $S$ itself is one of its substrings.

Input Specification

Each input file has several test cases.

The first line of the input file contains one integer $T$ $T$ denoting the number of test cases in the file.

In the following $T$ $T$ lines, each line contains a string $S$ $S$ consisting of lower-case English letters.

Output Specification

Output $T$ $T$ lines: each line consists of an integer denoting the total number of good partitions among all possible partitions of substrings of $S$ $S$ .

Sample Input 1

Copy

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

Sample Output 1

Copy

Explanation for Sample 1

Let $S[i,j]$ $S [i, j]$ denote the substring of $S$ $S$ consisting of the $i$ $i$ -th character to the $j$ $j$ -th character of $S$ $S$ , with index starting from $1$ $1$ .

In the first test case, there are three substrings admitting good partitions: $S[1,4] = \texttt{aabb}$ $S [1, 4] = aabb$ with $\texttt{A} = \texttt{a}, \texttt{B} = \texttt{b}$ $A = a, B = b$ , $S[3,6] = \texttt{bbbb}$ $S [3, 6] = bbbb$ with $\texttt{A} = \texttt{b}, \texttt{B} = \texttt{b}$ $A = b, B = b$ , and $S[1,6] = \texttt{aabbbb}$ $S [1, 6] = aabbbb$ with $\texttt{A} = \texttt{a}, \texttt{B} = \texttt{bb}$ $A = a, B = bb$ . Other substrings of $S$ $S$ do not admit good partitions, so the answer shall be $3$ $3$ .

In the second test case, $S[1,4] = S[2,5] = S[3,6] = \texttt{cccc}$ $S [1, 4] = S [2, 5] = S [3, 6] = cccc$ admit good partition $\texttt{A} = \texttt{c}, \texttt{B} = \texttt{c}$ $A = c, B = c$ , so the total contribution to the final answer is $3$ $3$ . For string $S[1,6] = \texttt{cccccc}$ $S [1, 6] = cccccc$ , it admits two good partitions ( $\texttt{A} = \texttt{c}, \texttt{B} = \texttt{cc}$ $A = c, B = cc$ or $\texttt{A} = \texttt{cc}, \texttt{B} = \texttt{c}$ $A = cc, B = c$ ). The different good partitions corresponding to the same substring should all count towards the final answer, so the final answer to the second test case is $3+2 = 5$ $3 + 2 = 5$ .

In the third test case, $S[1,8]$ $S [1, 8]$ and $S[4,11]$ $S [4, 11]$ admit two good partitions respectively. $S[1,8]$ $S [1, 8]$ is the example described in the problem description. The answer should be $2+2 = 4$ $2 + 2 = 4$ .

In the fourth test case, each of $S[1,4], S[6,11], S[7,12], S[2,11], S[1,8]$ $S [1, 4], S [6, 11], S [7, 12], S [2, 11], S [1, 8]$ admits one good partition, and $S[3,14]$ $S [3, 14]$ admits two good partitions, so the answer should be $5+2 = 7$ $5 + 2 = 7$ .

Attachment Package

The samples are available here.

Sample 2

See ex_excellent2.in and ex_excellent2.ans.

Sample 3

See ex_excellent3.in and ex_excellent3.ans.

Constraints

For all test cases, $1 \le T \le 10$ $1 \leq T \leq 10$ , $n \le 30\,000$ $n \leq 30 000$ .

Test case	$n \le$ $n \leq$	Special properties
1,2	$300$ $300$	All characters of $S$ $S$ are same.
3,4	$2\,000$ $2 000$	All characters of $S$ $S$ are same.
5,6	$10$ $10$	No additional constraints.
7,8	$20$ $20$
9,10	$30$ $30$
11,12	$50$ $50$
13,14	$100$ $100$
15	$200$ $200$
16	$300$ $300$
17	$500$ $500$
18	$1\,000$ $1 000$
19	$2\,000$ $2 000$
20	$30\,000$ $30 000$

Comments

There are no comments at the moment.