bzoj4650: [Noi2016]优秀的拆分 hash

好气啊，没开longlong又biubiu了

底层：

用hash或者奇奇怪怪的算法兹磁logn求最长公共前后缀

思路：

统计出从一个点开始和结束的形如AA的子串的个数

统计的时候把相邻的结果相乘加起来就好了

 1 #include <bits/stdc++.h>
 2 #define MOD 998244353
 3 #define ad(x,y,z) t[x][y]++,t[x][z+1]--
 4 using namespace std;
 5 long long T,n,LOG;
 6 char ch;
 7 long long a[50001],t[2][50001],mi[20];
 8 long long Mi[50001],ha[50001][20];
 9 int main()
10 {
11     for(scanf("%d",&T);T;T--)
12     {
13         for(ch=getchar();!isalpha(ch);ch=getchar());
14         for(n=0;isalpha(ch);ch=getchar())
15             a[++n]=ch-'a';
16         LOG=0;
17         for(int i=1;i<=n;i<<=1,++LOG) mi[LOG]=i;
18         Mi[1]=26;
19         for(int i=2;i<=n;i++)
20             Mi[i]=Mi[i-1]*26%MOD;
21         for(int i=1;i<=n;i++)
22             ha[i][0]=a[i];
23         for(int i=1;i<=LOG;i++)
24             for(int j=1;j<=n-mi[i]+1;j++)
25                 ha[j][i]=ha[j][i-1]*Mi[mi[i-1]]%MOD+ha[j+mi[i-1]][i-1];
26         for(int i=1;i<=n;i++)
27             t[0][i]=0,
28             t[1][i]=0;
29         for(int len=1;len<=n/2;len++)
30         {
31             for(int Now=1,Nex=1+len;Nex<=n;Now=Nex,Nex=Now+len)
32             {
33                 int now=Now,nex=Nex;
34                 for(int i=LOG;i>=0;i--)
35                 if(nex+mi[i]-1<=n)
36                     if(ha[now][i]==ha[nex][i])
37                         now+=mi[i],nex+=mi[i];
38                 int lcp=min(now-Now,len);
39                 now=Now,nex=Nex;
40                 for(int i=LOG;i>=0;i--)
41                 if(now>=mi[i])
42                     if(ha[now-mi[i]+1][i]==ha[nex-mi[i]+1][i])
43                         now-=mi[i],nex-=mi[i];
44                 int lcs=min(Now-now,len);
45                 now=Now,nex=Nex;
46                 if(lcp+lcs>=len)
47                 {
48                     ad(0,nex-lcs+len,nex+lcp-1);
49                     ad(1,now-lcs+1,now+lcp-len);
50                 }
51             }
52         }
53         for(int i=1;i<=n;i++)
54             t[0][i]+=t[0][i-1],
55             t[1][i]+=t[1][i-1];
56         long long ans=0;
57         for(int i=1;i<n;i++)
58             ans+=t[0][i]*t[1][i+1];
59         printf("%lld
",ans);
60     }
61     return 0;
62 }