80分求助
查看原帖
80分求助
490484
include13_fAKe楼主2023/7/21 14:29
#include<bits/stdc++.h>
using namespace std;

const int N=2e5;
const int jz=262144;
const int mod=998244353;
int n;
int zz[N];
int Hash[N];
int hash1[N];
int POW[N];
map<int,bool> m;
int f[N];
int calc(int l,int r){
	return Hash[r]-Hash[l-1]*POW[r-l+1];
}
int calc1(int l,int r){
	return hash1[l]-hash1[r+1]*POW[r-l+1];
}
int main(){
	cin>>n;
	POW[0]=1;
	for(int i=1;i<=n;i++){
		cin>>zz[i];
		Hash[i]=(zz[i]+(Hash[i-1]*jz)%mod+mod)%mod;
		POW[i]=(POW[i-1]*jz)%mod;
	}
	for(int i=n;i>=1;i--){
		hash1[i]=(zz[i]+(hash1[i+1]*jz)%mod+mod)%mod;
	}
	int final=0;
	int final_num;
	for(int k=1;k<=n;k++){
//		cout<<k<<endl;
		m.clear();
		int ans=0;
		for(int i=1;i+k-1<=n;i+=k){
			int j=i+k-1;
			if(m[calc(i,j)]==false||m[calc1(i,j)]==false){
				ans++;
				m[calc(i,j)]=m[calc1(i,j)]=true;
			}
		}
		f[k]=ans;
		if(f[k]>final){
			final=f[k];
			final_num=1;
		}
		else if(f[k]==final){
			final_num++;
		}
	} 
	cout<<final<<' '<<final_num<<endl;
	for(int i=1;i<=n;i++){
		if(f[i]==final){
			cout<<i<<' ';
		}
	}
	cout<<endl;
// 	for(int i=1;i<=n;i++){
// 		cout<<f[i]<<' ';
// 	}
	return 0;
} 
2023/7/21 14:29
加载中...