wannafly 挑战赛8 E 小G的项链（manecher）

链接：https://www.nowcoder.com/acm/contest/57/E

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 32768K，其他语言65536K
64bit IO Format: %lld

题目描述

有一串有n颗珠子的项链，每颗珠子上有一个数字，从顺时针方向看依次是第1，2，…，n个珠子，第n个珠子之后是第1个珠子。但是小G觉得这串项链的造型不够美观，他决定用这串项链上的珠子造出一个新的项链，并且他希望这串新的项链是对称的。

小G可以使用合成技术将任意正整数颗珠子合成为一个新的珠子，新珠子上的数字=原珠子上的数字的异或和。

小G希望新的项链上的珠子尽可能多，问新项链上的珠子最多有多少个。

输入描述:

第一行一个整数n。
第二行n个整数，第i个整数a

代表原项链上第i个珠子上的数字。

输出描述:

共一行一个整数，代表新项链的最大珠子数量。

输入例子:

5

9 3 9 1 1

输出例子:

5

-->

示例1

输入

5

9 3 9 1 1

输出

5

示例2

输入

9

7 8 6 5 4 3 1 2 15

输出

3

备注:

1 ≤ n ≤ 2e5,0<=ai<=1e9
////////////////////////////////////////////////////////////////////////////////

//////////////////////////////////////////////////////////////////////////////////////////

 #include <bits/stdc++.h>

 #define mst(a,b)    memset((a),(b), sizeof a)

 #define lowbit(a)   ((a)&(-a))

 #define IOS         ios::sync_with_stdio(0);cin.tie(0);

 #define MP          make_pair

 using namespace std;

 typedef long long ll;

 typedef pair<int,int> pii;

 const int mod=1e9+;

 const int maxn=4e5+;

 int n;

 int a[maxn],ps[maxn];

 int s[maxn],ma[maxn<<],mp[maxn<<];

 bool manacher(int ne){

     int len=ne*;

     for(int i=;i<ne;++i)s[ne+i]=s[i];

     int l=;

     ma[l++]=-;ma[l++]=-;

     for(int i=;i<len;++i)ma[l++]=s[i],ma[l++]=-;

     ma[l]=-;

     int mx=,id=;

     for(int i=;i<l;++i){

         mp[i]=mx>i?min(mp[*id-i],mx-i):;

         while(ma[i+mp[i]]==ma[i-mp[i]])++mp[i];

         if(mp[i]->=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[];

     return ps[en]^ps[st];

 }

 int main(){

 #ifdef local

 freopen("in.txt","r",stdin);

 //freopen("out.txt","w",stdout);

 #endif

     scanf("%d",&n);

     for(int i=;i<=n;++i)scanf("%d",&a[i]),ps[i]=ps[i-]^a[i];

     for(int k=;k<=n;++k){

         if(n%k!=)continue;

         int ans=n/k;

         for(int i=;i<k;++i){

             for(int j=;j<ans;++j)

                 s[j]=get(j*k+i,(j+)*k+i);

             if(manacher(ans))return *printf("%d",ans);

         }

     }

     return ;

 }