Interesting

Time Limit: 30 Sec Memory Limit: 256 MB

Description

img

Alice get a string S. She thinks palindrome string is interesting. Now she wanna know how many three tuple (i,j,k) satisfy , S[i…j] and S[j+1…k] are all palindrome strings. It’s easy for her. She wants to know the sum of i*k of all required three tuples. She can’t solve it. So can you help her? The answer may be very large, please output the answer mod 1000000007.

A palindrome string is a string that is same when the string is read from left to right as when the string is read from right to left.

Input

img

Output

img

Sample Input

2
　　aaa
　　abc

Sample Output

14
　　8

HINT

img

Source

我们先找一下这道题的本质，根据乘法分配律，我们可以使得：cntL[i]表示以 i 开始的是回文串的下标和，cntR[i]表示以 i 结束的回文串的下标和，那么这时候答案显然就是cntR[i]×cntL[i+1]。

我们再来思考一下怎么求出cntL和cntR，显然我们可以运用Manacher算法O(n)得到每一个回文半径，然后 i 对于cntL和cntR的影响显然就是一个序列上的等差数列。

接着我们再记录一下del表示公差，O(n)推一下等差数列每个位置的和即可。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = (1e6+5)*2;
const int MOD = 1e9+7;
const int Niyu = 5e8+4;

int T;
int cntL[ONE],delL[ONE],l;
int cntR[ONE],delR[ONE],r;
char s[ONE],a[ONE];
int p[ONE],n;
int Ans;

int get()
{
    int res=1,Q=1;  char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

void Deal_first()
{
    a[0] = '(';
    for(int i=1;i<=n;i++)
    {
        a[2*i-1] = '#';
        a[2*i] = s[i];
    }
    n = 2 * n + 1;
    a[n] = '#';    a[n+1] = ')';
}

void Manacher()
{
    int l = 0, id = 0;
    for(int i=1;i<=n;i++) p[i] = 0;
    for(int i=1;i<=n;i++)
    {
        if(l >= i) p[i] = min(p[id + id - i], l - i);
        else p[i] = 1;
        while(a[i-p[i]] == a[i+p[i]]) p[i]++;
        if(p[i] + i > l) l = p[i]+i, id = i;
    }
}

void Add(int &a,int b) {a+=b;    if(a>0) a-=MOD;    if(a<0) a+=MOD;}

void Solve()
{
    scanf("%s",s+1);    n=strlen(s+1);
    Deal_first();    Manacher();

    for(int i=1;i<=n;i++) cntL[i]=cntR[i]=delL[i]=delR[i]=0;

    for(int i=1;i<=n;i++)
    {
        l = i-p[i]+1;    r = i+p[i]-1;
        Add(cntL[l], r);    Add(cntL[i+1], -r+(i-l));    Add(delL[l+1], -1);    Add(delL[i+1], 1);
        Add(cntR[i], i);    Add(cntR[r+1], -i+(r-i));    Add(delR[i+1], -1);    Add(delR[r+1], 1);
    }

    for(int i=1;i<=n;i++)
    {
        Add(cntL[i],cntL[i-1]);    Add(delL[i],delL[i-1]);    Add(cntL[i],delL[i]);
        Add(cntR[i],cntR[i-1]);    Add(delR[i],delR[i-1]);    Add(cntR[i],delR[i]);
    }

    n=strlen(s+1);
    Ans = 0;
    for(int i=1;i<n;i++)
    {
        Ans = Ans + (s64)cntR[2*i] *Niyu%MOD * cntL[2*(i+1)]%MOD *Niyu%MOD ;
        Add(Ans,0);
    }

    printf("%d\n",Ans);
}

int main()
{
    T=get();
    while(T--)
        Solve();
}