首先,维护每个特征出现次数的前缀和, 表示在 中特征 出现的次数。显然 为平衡段当且仅当:
进一步,我们发现,若有四个特征,前 头牛分别出现了: 次,,前 头牛分别出现了: 次,那么可以使 这四个数字同时减去 ,使第一位变成零,得:
同理, 同时减去 ,得: .故 为平衡段
不难发现,若 为平衡段,那么 和 在同时减去某个数使 和 为 时两个前缀和数组是一样的。
将 在同时减去某个数使 为 时的数组称为差值数组
可以用临时数组 做为前 头牛的差值数组,用 记录达成此状态的位置,若发现两个状态相同,则更新答案。具体参照代码。
#include<bits/stdc++.h>
using namespace std;
#define int long long
map<vector<int>,int> M;
signed main(){
int n,m,ans=0;
cin>>n>>m;
vector<int> V(m);
M[V]=0;
for(int i=1;i<=n;i++){
int x,pos=0;
cin>>x;
while(pos<m){
if(x&1){
V[pos]++;
if(pos==m-1&&x==1){
for(int j=0;j<m;j++){
V[j]--;
}
break;
}
}
pos++;
x>>=1;
}
if(M.count(V)){
ans=max(ans,i-M[V]);
}else{
M[V]=i;
}
}
cout<<ans<<endl;
return 0;
}