不知道问题出在哪里求助(玄关)
查看原帖
不知道问题出在哪里求助(玄关)
1287433
__ycy1124__楼主2024/7/15 10:05
#include<bits/stdc++.h>
using namespace std;
unsigned long long qzh[200001],hzh[400001],base=1000007,md=1333331,w[200001];
int a[200005];
int ans,bj[200001],ansj;
void read(int &x){
	x=0;
	int f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){
		if(ch=='-'){
			f=-f;
		}
		ch=getchar();
	}
	while(ch>='0'&&ch<='9'){
		x*=10;
		x+=ch-'0';
		ch=getchar();
	}
	x*=f;
}
int main(){
	int n;
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		read(a[i]);
	}
	w[0]=1;
	for(int i=1;i<=n;i++){
		qzh[i]=(qzh[i-1]*base+a[i])%md;
		hzh[n-i+1]=(hzh[n-i+2]*base+a[i])%md;
		w[i]=w[i-1]*base;
	}
	set <unsigned long long> s;
	for(int i=1;i<=n&&n/i>=ans;i++){
		int js=0;
		s.clear();
		for(int j=i;j<=n;j+=i){
			unsigned long long x1,x2;
			//cout<<x1<<' '<<x2<<'\n';
			x1=qzh[j]-qzh[j-i-1]*w[i];
			x2=hzh[j]-hzh[j+i+1]*w[i];
			if(s.count(x1)){
			}
			else{
				s.insert(x1);
				js++;
			}
			if(s.count(x2)){
			}
			else{
				s.insert(x2);
				js++;
			}
		}
		if(js==ans){
			bj[++ansj]=i;
		}
		else if(js>ans){
			ans=js;
			ansj=0;
			bj[++ansj]=i;
		}
	}
	printf("%d %d\n",ans,ansj);
	for(int i=1;i<=ansj;i++){
		printf("%d ",bj[i]);
	}
	return 0;
}
2024/7/15 10:05
加载中...