如果一个字符串可以被拆分为 AABB AABB 的形式，其中 A A 和 B B 是任意非空字符串，则我们称该字符串的这种拆分是优秀的。
例如，对于字符串 aabaabaa，如果令 A=aab A=aab， B=a B=a，我们就找到了这个字符串拆分成 AABB AABB 的一种方式。
一个字符串可能没有优秀的拆分，也可能存在不止一种优秀的拆分。比如我们令 A=a A=a， B=baa B=baa，也可以用 AABB AABB 表示出上述字符串；但是，字符串 abaabaa 就没有优秀的拆分。
现在给出一个长度为 n n 的字符串 S S，我们需要求出，在它所有子串的所有拆分方式中，优秀拆分的总个数。这里的子串是指字符串中连续的一段。
以下事项需要注意：
出现在不同位置的相同子串，我们认为是不同的子串，它们的优秀拆分均会被记入答案。在一个拆分中，允许出现 A=B A=B。例如 cccc 存在拆分 A=B=c A=B=c。字符串本身也是它的一个子串。每个输入文件包含多组数据。输入文件的第一行只有一个整数 T T，表示数据的组数。保证 1≤T≤10 1≤T≤10。
接下来 T T 行，每行包含一个仅由英文小写字母构成的字符串 S S，意义如题所述。
输出 T T 行，每行包含一个整数，表示字符串 S S 所有子串的所有拆分中，总共有多少个是优秀的拆分。
我们用 S[i,j] S[i,j] 表示字符串 S S 第 i i 个字符到第 j j 个字符的子串（从 1 1 开始计数）。
第一组数据中，共有 3 3 个子串存在优秀的拆分：
S[1,4]=aabb S[1,4]=aabb，优秀的拆分为 A=a A=a， B=b B=b；
S[3,6]=bbbb S[3,6]=bbbb，优秀的拆分为 A=b A=b， B=b B=b；
S[1,6]=aabbbb S[1,6]=aabbbb，优秀的拆分为 A=a A=a， B=bb B=bb。
而剩下的子串不存在优秀的拆分，所以第一组数据的答案是 3 3。
第二组数据中，有两类，总共 4 4 个子串存在优秀的拆分：
对于子串 S[1,4]=S[2,5]=S[3,6]=cccc S[1,4]=S[2,5]=S[3,6]=cccc，它们优秀的拆分相同，均为 A=c A=c， B=c B=c，但由于这些子串位置不同，因此要计算 3 3 次；
对于子串 S[1,6]=cccccc S[1,6]=cccccc，它优秀的拆分有 2 2 种： A=c A=c， B=cc B=cc 和 A=cc A=cc， B=c B=c，它们是相同子串的不同拆分，也都要计入答案。
所以第二组数据的答案是 3+2=5 3+2=5。
第三组数据中， S[1,8] S[1,8] 和 S[4,11] S[4,11] 各有 2 2 种优秀的拆分，其中 S[1,8] S[1,8] 是问题描述中的例子，所以答案是 2+2=4 2+2=4。
第四组数据中， S[1,4] S[1,4]， S[6,11] S[6,11]， S[7,12] S[7,12]， S[2,11] S[2,11]， S[1,8] S[1,8] 各有 1 1 种优秀的拆分， S[3,14] S[3,14] 有 2 2 种优秀的拆分，所以答案是 5+2=7 5+2=7。
见样例数据下载。
见样例数据下载。
对于全部的测试点,保证 1≤T≤10 1≤T≤10。以下对数据的限制均是对于单组输入数据而言的，也就是说同一个测试点下的 T T 组数据均满足限制条件。
我们假定 n n 为字符串 S S 的长度，每个测试点的详细数据范围见下表：
测试点编号 n n 其他约束 1、2 ≤300 ≤300 S S中所有字符全部相同 3、4 ≤2000 ≤2000 5、6 ≤10 ≤10 无 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 ≤1000 ≤1000 19 ≤2000 ≤2000 20 ≤30000 ≤30000时间限制： 1.5s 1.5s
空间限制： 512MB 512MB
样例数据下载
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~hash~
hash大法好！
95分O(n^2)做法：我们枚举中间位置i，然后求出它左右的aa的个数，左右相乘加入答案。
代码当然也是95的哼
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; #define ll long long const int jin=27; int t,n,f[2001],kk[2001]; ll l,r,now1,now2,ans; char s[2001]; int main() { scanf("%d",&t); kk[0]=1; for(int i=1;i<=2000;i++) kk[i]=kk[i-1]*jin; while(t--) { scanf("%s",s+1);ans=0; n=strlen(s+1); for(int i=1;i<=n;i++) f[i]=f[i-1]*jin+s[i]-'a'; for(int i=2;i<n-1;i++) { l=r=0; for(int j=i/2;j;j--) { now1=f[i]-f[i-j]*kk[j]; now2=f[i-j]-f[i-j*2]*kk[j]; l+=(now1==now2); } for(int j=(n-i)/2;j;j--) { now1=f[i+j]-f[i]*kk[j]; now2=f[i+j*2]-f[i+j]*kk[j]; r+=(now1==now2); } ans+=l*r; } printf("%lld\n",ans); } return 0; }
