相似回文串

Time Limit: 10 Sec  Memory Limit: 128 MB
Submit: 143  Solved: 68
[Submit][Status][Discuss]

Description

记S(i,j)为字符串S的第i个字母到第j个字母组成的子串。
给出一个长度为n由小写英文字母组成的字符串A。
若字符串B也由小写英文字母组成,长度为n,且对于任意1<=i<j<=n有:若A(i,j)是回文串,B(i,j)也是回文串;若A(i,j)不是回文串,B(i,j)也不是回文串。那么我们称B与A是ayq相似的。
求有多少个字符串与A ayq相似?输出答案对1000000007取模的余数。
 

Input

输入1行一个字符串A
 

Output

 
输出一行一个数表示所求答案
 

Sample Input

abcba

Sample Output

15600

HINT

对于100%的数据,n<=1000000

用Manacher可以推出O(n)对相等和不等关系。

将相等的用并查集维护,不等的连边。

然后从1到n,如果该等价类还没被考虑过,则ans*=26-与它不等的考虑过的等价类个数。

 #include<cstring>
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<queue>
#include<vector> #define N 1000007
#define mod 1000000007
#define fzy pair<int,int>
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while(!isdigit(ch)){if(ch=='-')f=-;ch=getchar();}
while(isdigit(ch)){x=(x<<)+(x<<)+ch-'';ch=getchar();}
return x*f;
} int n,m;
int i,r,p,f[N<<],fa[N],vis[N],ans=;
char a[N],s[N<<],col[N];
struct E{
int v;
E*nxt;
}*j,*h[N],pool[N<<],*cur=pool; int find(int x)
{
return fa[x]==x?x:fa[x]=find(fa[x]);
}
inline void merge(int x,int y)
{
if(x&)return;
if(find(x>>=)==find(y>>=))return;
fa[fa[x]]=fa[y];
}
inline void add(int x,int y)
{
if(!x||!y||x&)return;
j=cur++;j->v=y>>;j->nxt=h[x>>=];h[x]=j;
}
int main()
{
scanf("%s",a+),n=strlen(a+);
for(i=;i<=n;i++)
fa[i]=i;
for(i=;i<=n;i++)
s[i<<]=a[i],s[i<<|]='#';
s[]='$',s[]='#',s[m=(n+)<<]='@';
for(f[]=,i=;i<m;i++)
{
for(f[i]=r>i?min(r-i,f[p*-i]):;s[i-f[i]]==s[i+f[i]];f[i]++) merge(i+f[i],i-f[i]);
add(i+f[i],i-f[i]);
if(i+f[i]>r)r=i+f[i],p=i;
}
for(i=;i<=n;i++)
if(!col[find(i)])
{
for(p=,j=h[i];j;j=j->nxt)
if(col[find(j->v)]) if(vis[fa[j->v]]<i) vis[fa[j->v]]=i,p--;
col[fa[i]]=,ans=1LL*ans*p%;
}
printf("%d",ans);
}
05-11 22:13