# CodeForces 17E Palisection(回文树)

E. Palisection

time limit per test

2 seconds

memory limit per test

128 megabytes

input

standard input

output

standard output

In an English class Nick had nothing to do at all, and remembered about wonderful strings called palindromes. We should remind you that a string is called a palindrome if it can be read the same way both from left to right and from right to left. Here are examples of such strings: «eye», «pop», «level», «aba», «deed», «racecar», «rotor», «madam».

Nick started to look carefully for all palindromes in the text that they were reading in the class. For each occurrence of each palindrome in the text he wrote a pair — the position of the beginning and the position of the ending of this occurrence in the text. Nick called each occurrence of each palindrome he found in the text subpalindrome. When he found all the subpalindromes, he decided to find out how many different pairs among these subpalindromes cross. Two subpalindromes cross if they cover common positions in the text. No palindrome can cross itself.

Let's look at the actions, performed by Nick, by the example of text «babb». At first he wrote out all subpalindromes:

• «b» — 1..1 • «bab» — 1..3 • «a» — 2..2 • «b» — 3..3 • «bb» — 3..4 • «b» — 4..4

Then Nick counted the amount of different pairs among these subpalindromes that cross. These pairs were six:

1. 1..1 cross with 1..3 2. 1..3 cross with 2..2 3. 1..3 cross with 3..3 4. 1..3 cross with 3..4 5. 3..3 cross with 3..4 6. 3..4 cross with 4..4

Since it's very exhausting to perform all the described actions manually, Nick asked you to help him and write a program that can find out the amount of different subpalindrome pairs that cross. Two subpalindrome pairs are regarded as different if one of the pairs contains a subpalindrome that the other does not.

Input

The first input line contains integer n (1 ≤ n ≤ 2·106) — length of the text. The following line contains n lower-case Latin letters (from ato z).

Output

In the only line output the amount of different pairs of two subpalindromes that cross each other. Output the answer modulo 51123987.

Examples

input

```4
babb```

output

`6`

input

```2
aa```

output

`2`

```#include <iostream>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
#include <math.h>
#include <stdio.h>

using namespace std;
typedef long long int LL;
const int MAX=2*1e6;
const int mod=51123987;
int n;
char str[MAX+5];
int sum[MAX+5];
{
int u[MAX+5];int v[MAX+5];
int tot;
void clear()
{
tot=0;
}
int get(int x,int y)
{
{
if(u[i]==y)
return v[i];
}
return 0;
}
void insert(int x,int y,int z)
{
u[tot]=y;  v[tot]=z;
}

};
struct Tree
{
//int next[MAX+5][26];
int fail[MAX+5];//指向当前节点回文串中最长的后缀回文子串
int cnt[MAX+5];//当前节点的回文串一共有多少个
int num[MAX+5];//当前节点为结尾的回文子串的个数
int len[MAX+5];//当前节点的回文串的长度
int s[MAX+5];//字符串
int last;//回文树最后一个节点
int n;
int p;//回文树当前有多少个节点
int new_node(int x)
{
//memset(next[p],0,sizeof(next[p]));
cnt[p]=0;
next.clear(p);
num[p]=0;
len[p]=x;
return p++;
}

void init()
{
next.clear();
p=0;
new_node(0);
new_node(-1);
last=0;
n=0;
s[0]=-1;
fail[0]=1;
}

int get_fail(int x)
{
while(s[n-len[x]-1]!=s[n])
x=fail[x];
return x;
}

{
x-='a';
s[++n]=x;
int cur=get_fail(last);
if(!(last=next.get(cur,x)))
{
int now=new_node(len[cur]+2);
fail[now]=next.get(get_fail(fail[cur]),x);
next.insert(cur,x,now);
num[now]=num[fail[now]]+1;
last=now;
}
cnt[last]++;
return num[last];
}
LL Allsum()//求出所有回文子串的数目
{
LL ret=0;

for(int i=p-1;i>0;i--)
{
cnt[fail[i]]=(cnt[fail[i]]+cnt[i])%mod;

ret=(ret+cnt[i])%mod;
}
return ret;
}
}tree;
int main()
{
scanf("%d",&n);
scanf("%s",str);
tree.init();
sum[n]=0;
for(int i=n-1;i>=0;i--)
tree.init();
LL ans=0;LL res=0;LL res2=0;
for(int i=0;i<=n-1;i++)
{
res2+=tree.num[tree.last];//同样也可以求所有回文子串的数目
}
res=tree.Allsum();
//cout<<res<<" "<<res2<<endl;两个是相等的
ans=(((LL)res*(res-1)/2%mod-ans)%mod+mod)%mod;
printf("%lld\n",ans);
return 0;
}```

0 条评论

## 相关文章

### SQL中GROUP BY用法示例

GROUP BY我们可以先从字面上来理解，GROUP表示分组，BY后面写字段名，就表示根据哪个字段进行分组，如果有用Excel比较多的话，GROUP BY比较类...

5.2K20

51620

13750

12310

44830

18430

16220

30740

35230

22440