NOI '16 P1 - Good Partitions

View as PDF

Submit solution

Points: 20 (partial)
Time limit: 1.5s
Memory limit: 512M

Problem type

If a string can be written in the form of \texttt{AABB} where \texttt{A} and \texttt{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} in the form of \texttt{AABB} by letting \texttt{A} = \texttt{aab} and \texttt{B} = \texttt{a}.

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

Given a string S of length 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} in a good partition. For example, the string \texttt{cccc} admits good partition \texttt{A} = \texttt{B} = \texttt{c}.
  • The string 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 denoting the number of test cases in the file.

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

Output Specification

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

Sample Input 1

4
aabbbb
cccccc
aabaabaabaa
bbaabaababaaba

Sample Output 1

3
5
4
7

Explanation for Sample 1

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

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

In the second test case, S[1,4] = S[2,5] = S[3,6] = \texttt{cccc} admit good partition \texttt{A} = \texttt{c}, \texttt{B} = \texttt{c}, so the total contribution to the final answer is 3. For string S[1,6] = \texttt{cccccc}, it admits two good partitions (\texttt{A} = \texttt{c}, \texttt{B} = \texttt{cc} or \texttt{A} = \texttt{cc}, \texttt{B} = \texttt{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.

In the third test case, S[1,8] and S[4,11] admit two good partitions respectively. S[1,8] is the example described in the problem description. The answer should be 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] admits one good partition, and S[3,14] admits two good partitions, so the answer should be 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, n \le 30\,000.

Test casen \leSpecial properties
1,2300All characters of S are same.
3,42\,000
5,610No additional constraints.
7,820
9,1030
11,1250
13,14100
15200
16300
17500
181\,000
192\,000
2030\,000

Comments

There are no comments at the moment.