题解 P3449 【[POI2006]PAL-Palindromes】
bymhq
2019-07-30 20:34:42
看到这道题后想了一个~~证不出来~~的结论，交了一下竟然过了。
然后查题解找证明没有找到。。。如果有大佬会证明方法，请不吝赐教%%%。
结论是：
**当且只当，a、b两个回文串的最小循环节一样时，a+b是回文串。**
（这里最小循环节长度必须为回文串的约数）
比如ababa和aba的最小循环节分别为ababa、aba，不一样所以ababaaba不是回文串
abaaba和abaabaaba的最小循环节分别为aba，一样所以连起来是回文串；
因为如果s是回文串，所以s的最小循环节是回文串。
之后就不太会证了qwq
当然，有可能结论根本就是错的，可蒟蒻找不到hack的数据
下面是code，大佬帮忙hack
```cpp
#include<bits/stdc++.h>
#define ll long long
#define u unsigned int
using namespace std;
const u bas=233;
int n,m;
u hsh[2000100],now,k[2000100];
char a[2000100];
u hh(int l,int r){return hsh[r]-hsh[l-1]*k[r-l+1];}
bool pd(int x)
{//cout<<now<<" "<<x<<endl;
for(register int i=1;i<=m;i+=x){//cout<<hh(i,i+x-1)<<" ";
if(hh(i,i+x-1)!=now)return 0;}return 1;
}
main()
{
scanf("%d",&n);k[0]=1;
multiset<u>s;for(int i=1;i<=2e6;i++)k[i]=k[i-1]*bas;
for(int ii=1;ii<=n;ii++)
{
scanf("%d",&m);
scanf("%s",a+1);
for(int i=1;i<=m;i++)
hsh[i]=hsh[i-1]*bas+a[i];
for(int i=1;i<=m;i++)
{
if(m%i)continue;
now=hh(1,i);
if(pd(i))
{//cout<<endl;
s.insert(now);break;
}//cout<<endl;
}
}
ll ans=0;
while(!s.empty())
{
int o=*s.lower_bound(0),oo=s.count(o);//cout<<oo<<endl;
ans+=(ll)oo*oo;s.erase(o);
}cout<<ans;
}
```