多校1005 HDU5785 Interesting (manacher)

  1 // 多校1005 HDU5785 Interesting
  2 // 题意：给你一个串，求相邻两个回文串左边端点*右边端点的和
  3 // 思路：马拉车算出最长回文半径，求一个前缀和，既得到每个点对答案的贡献。
  4 // ans=L[i]*R[i-1]
  5 // L[i] 以i开始的所有回文串结尾坐标的和
  6 // R[i] 以i结尾的所有回文串开始坐标的和
  7 // 这题我们关键是求L[] R[]
  8 // 另开两个数组a[] b[] 分别记录当前点对答案贡献 和每个点出现的次数
  9 
 10 
 11 // #pragma comment(linker, "/STACK:102c000000,102c000000")
 12 #include <iostream>
 13 #include <cstdio>
 14 #include <cstring>
 15 #include <sstream>
 16 #include <string>
 17 #include <algorithm>
 18 #include <list>
 19 #include <map>
 20 #include <vector>
 21 #include <queue>
 22 #include <stack>
 23 #include <cmath>
 24 #include <cstdlib>
 25 // #include <conio.h>
 26 using namespace std;
 27 #define clc(a,b) memset(a,b,sizeof(a))
 28 #define inf 0x3f3f3f3f
 29 #define lson l,mid,rt<<1
 30 // #define rson mid+1,r,rt<<1|1
 31 const int N = 1e6+10;
 32 const int MOD = 1e9+7;
 33 #define LL long long
 34 #define LB long double
 35 // #define mi() (l+r)>>1
 36 double const pi = acos(-1);
 37 const double eps = 1e-8;
 38 void fre(){freopen("in.txt","r",stdin);}
 39 inline int read(){int x=0,f=1;char ch=getchar();while(ch>'9'||ch<'0') {if(ch=='-') f=-1;ch=getchar();}while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}return x*f;}
 40 
 41 char str[N];
 42 char s[N<<1];
 43 int Len[N<<1];
 44 void Manacher(int n){
 45     clc(s,'#');
 46     for(int i=0;i<n;i++)  
 47         s[i*2+2]=str[i];  
 48         int len=n*2+1;s[0]='$';  
 49         int mx=0,po=0;  
 50         for(int i=1;i<=len;i++)  {
 51             if(mx>i)  
 52                 Len[i]=min(Len[po*2-i],mx-i);  
 53             else Len[i]=1;  
 54             while(s[i+Len[i]]==s[i-Len[i]])  Len[i]++;  
 55             if(i+Len[i]>mx) { mx=i+Len[i];po=i;}  
 56         }  
 57 }
 58 
 59 LL a[N<<1],b[N<<1];
 60 LL L[N],R[N];
 61 int main(){
 62     while(~scanf("%s",str)){
 63         int len=strlen(str);
 64         Manacher(len);
 65         len=(len<<1)+1;
 66         for(int i=0;i<=len;i++) a[i]=0,b[i]=0;
 67         for(int i=len;i>=1;i--){
 68             a[i-Len[i]+1]+=i;
 69             a[i+1]-=i;
 70             b[i-Len[i]+1]++;
 71             b[i+1]--;
 72         } 
 73         LL a1=0,a2=0;
 74         for(int i=1;i<=len;i++){
 75             a1+=a[i],a2+=b[i];
 76             if(i%2==0)
 77             L[i/2]=(a1-a2*i/2)%MOD;
 78         }
 79 
 80         for(int i=0;i<=len;i++) a[i]=0,b[i]=0;
 81         a1=0,a2=0;
 82         for(int i=len;i>=1;i--){
 83             a[i]+=i;
 84             a[i+Len[i]]-=i;
 85             b[i]++;
 86             b[i+Len[i]]--;
 87         }
 88         for(int i=1;i<=len;i++){
 89             a1+=a[i],a2+=b[i];
 90             if(i%2==0)
 91             R[i/2]=(a1-a2*i/2)%MOD;
 92         }
 93 
 94         LL ans=0;
 95         for(int i=2;i<=len/2;i++){
 96             ans=(ans+L[i]*R[i-1]%MOD)%MOD;
 97         }
 98         printf("%I64d
",ans);
 99     }
100     return 0;
101 }