C++14(g++5.4) 解法, 执行用时: 54ms, 内存消耗: 11624K, 提交时间: 2020-06-02 23:04:35

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=4e5+10;
int n;
int a[maxn],ps[maxn];
int s[maxn],ma[maxn<<1],mp[maxn<<1];
bool manacher(int ne)
{
    int len=ne*2;
    for(int i=0; i<ne; ++i)
        s[ne+i]=s[i];
    int l=0;
    ma[l++]=-1;
    ma[l++]=-2;
    for(int i=0; i<len; ++i)
        ma[l++]=s[i],ma[l++]=-2;
    ma[l]=-88;
    int mx=0,id=0;
    for(int i=0; i<l; ++i)
    {
        mp[i]=mx>i?min(mp[2*id-i],mx-i):1;
        while(ma[i+mp[i]]==ma[i-mp[i]])
            ++mp[i];
        if(mp[i]-1>=ne)
            return true;
        if(i+mp[i]>mx)
            mx=i+mp[i],id=i;
    }
    return false;
}
int get(int st,int en)
{
    if(en>n)
        return ps[n]^ps[st]^ps[en-n]^ps[0];
    return ps[en]^ps[st];
}
int main()
{
    scanf("%d",&n);
    for(int i=1; i<=n; ++i)
        scanf("%d",&a[i]),ps[i]=ps[i-1]^a[i];
    for(int k=1; k<=n; ++k)
    {
        if(n%k!=0)
            continue;
        int ans=n/k;
        for(int i=0; i<k; ++i)
        {
            for(int j=0; j<ans; ++j)
                s[j]=get(j*k+i,(j+1)*k+i);
            if(manacher(ans))
                return 0*printf("%d",ans);
        }
    }
    return 0;
}

C++11(clang++ 3.9) 解法, 执行用时: 78ms, 内存消耗: 8448K, 提交时间: 2018-01-20 13:30:37

#include<cstdio>
#include<algorithm>
using namespace std;
const int N=4e5+88;
int n,S[N],a[N],p[N],Xor[N];
bool mar(int length) {
	S[0]=-5,S[length+1]=-6;
	int id=0,mx=0,ans=0;
	for(int i=1;i<=length;++i) {
		if(mx>i) p[i]=min(mx-i,p[2*id-i]);else p[i]=1;
		while(S[i-p[i]]==S[i+p[i]]) ++p[i];
		if(i+p[i]>mx) mx=i+p[i],id=i;
        ans=max(ans,p[i]);		
	}
	return ans>=length/4;
}
bool solve(int y){
	for(int i=1;i<=y;++i) {
		int tot=0;
		for(int j=i;j<=i+2*n-1;j+=y) S[++tot]=Xor[j+y-1]^Xor[j-1];
		if(mar(tot)) return 1;
	}
	return 0;
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i) scanf("%d",&a[i]),a[i+n]=a[i];
	for(int i=1;i<=2*n;++i) Xor[i]=a[i],Xor[i]^=Xor[i-1];
	for(int i=1;i<=n;++i) if(n%i==0) if(solve(i)) {
		printf("%d\n",n/i);break;
	}
}