BZOJ1524: [POI2006]Pal hash+恶心题

题解：

玛德现在我做什么题感觉什么题恶心。。

一定是我心态不对。

这题就随便分类讨论一下就行了。

假设$x+y$是一个回文串。

若$len_x=len_y$，必定有$x=y$。

若$len_x>len_y$，$y$必定是$x$的前缀，且剩下的部分是回文串。

若$len_x<len_y$，$x$必定是$y$的后缀，且剩下的部分是回文串。

我们只需要枚举比较长的串，然后利用hash随便判判就行了。

然而hash各种卡，又WA又T一时爽。。。

为了保证正确性写的双hash，现在依然在T中QoQ。

代码：

#include<cstdio>
#include<cstring>
#include<cctype>
#include<iostream>
#include<algorithm>
#include<map>
#include<ctime>
using namespace std;

typedef long long ll;
#define N 2000010
int id,be[N],en[N],tot;
char s[N],rs[N],tmp[N];
int f1[N],rf1[N],pow1[N];
int f2[N],rf2[N],pow2[N];

static const int seed1=233;
static const int mod1=1000000007;
static const int seed2=2333;
static const int mod2=1000000009;
//static const int seed3=131;
//static const int mod3=998244353;

typedef pair<int,int> pii;
#define mp make_pair

pii get(int l,int r){
	int hash1=(f1[l]-(ll)f1[r+1]*pow1[r-l+1]%mod1+mod1)%mod1;
	int hash2=(f2[l]-(ll)f2[r+1]*pow2[r-l+1]%mod2+mod2)%mod2;
	//printf("%d %d\n",hash1,hash2);
	return mp(hash1,hash2);
}

pii getr(int l,int r){
	int hash1=(rf1[l]-(ll)rf1[r+1]*pow1[r-l+1]%mod1+mod1)%mod1;
	int hash2=(rf2[l]-(ll)rf2[r+1]*pow2[r-l+1]%mod2+mod2)%mod2;
	return mp(hash1,hash2);
}

//map<pii,int>M;
struct Hashset{
	static const int Mod=131313;
	int head[Mod],next[N],v[N],ind;
	pii f[N];
	void reset(){
		ind=0;
		memset(head,-1,sizeof head);
	}
	void insert(pii x){
		int ins=(x.first+x.second)%Mod;
		for(int j=head[ins];j!=-1;j=next[j])
			if(f[j]==x){
				++v[j];
				return;
			}
		f[ind]=x;
		v[ind]=1;
		next[ind]=head[ins];
		head[ins]=ind++;
	}
	int operator[](pii x){
		int ins=(x.first+x.second)%Mod;
		for(int j=head[ins];j!=-1;j=next[j])
			if(f[j]==x)
				return v[j];
		return 0;
	}
}M;

bool check(int l,int r){
	if(l==r)
		return 1;
	int hl=(r-l+1)>>1;
	return get(l,l+hl-1)==getr(tot-r+1,tot-r+hl);
}

int main(){
	//clock_t beg=clock();
#ifndef ONLINE_JUDGE
	//freopen("tt.in","r",stdin);
#endif
	int n,i,j,len;
	scanf("%d",&n);
	for(i=1;i<=n;++i){
		scanf("%d%s",&len,tmp+1);
		++id;
		be[id]=en[id-1]+1;
		en[id]=en[id-1]+len;
		for(j=1;j<=len;++j)
			s[++tot]=tmp[j];
	}
	memcpy(rs,s,sizeof s);
	for(i=1;i<=(tot>>1);++i)
		swap(rs[i],rs[tot-i+1]);
	
	for(pow1[0]=pow2[0]=1,i=1;i<=tot;++i){
		pow1[i]=(ll)pow1[i-1]*seed1%mod1;
		pow2[i]=(ll)pow2[i-1]*seed2%mod2;
	}
	
	for(i=tot;i>=1;--i){
		f1[i]=((ll)f1[i+1]*seed1+(s[i]-'a'+1))%mod1;
		rf1[i]=((ll)rf1[i+1]*seed1+(rs[i]-'a'+1))%mod1;
		f2[i]=((ll)f2[i+1]*seed2+(s[i]-'a'+1))%mod2;
		rf2[i]=((ll)rf2[i+1]*seed2+(rs[i]-'a'+1))%mod2;
	}
	
	M.reset();
	for(i=1;i<=n;++i)
		M.insert(get(be[i],en[i]));
		//M[get(be[i],en[i])]++;
	
	long long ans=0;
	for(i=1;i<=n;++i){
		ans+=M[get(be[i],en[i])];
		for(j=be[i];j<en[i];++j)
			if(check(j+1,en[i]))
				ans+=M[get(be[i],j)];
		for(j=tot-en[i]+1;j<tot-be[i]+1;++j)
			if(check(be[i],tot-j))
				ans+=M[getr(tot-en[i]+1,j)];
	}
	
	cout<<ans<<endl;
	//printf("%ldms\n",clock()-beg);
	return 0;
}