C++14(g++5.4) 解法, 执行用时: 599ms, 内存消耗: 9564K, 提交时间: 2019-12-08 16:40:18

#include<bits/stdc++.h>
using namespace std;
const int P = 1e9+7;

int main() {
  ios::sync_with_stdio(false);
  int n; cin >> n;
  vector<int> A(n); for (auto &a: A) cin >> a;
  vector<int> H(n+1); for (int i = 0; i < n; i++) H[i+1] = H[i] * P + A[i];
  vector<int> I(n+1); for (int i = n - 1; i >= 0; i--) I[i] = I[i + 1] * P + A[i];
  vector<int> B(n+1); B[0] = 1; for (int i = 0; i < n; i++) B[i+1] = B[i] * P;
  int best = 0;
  vector<int> ans;
  for (int k = 1; k <= n; k++) {
    set<pair<int, int>> S;
    for (int i = 0; i + k <= n; i += k) {
      int l = (H[i+k] - H[i]*B[k]);
      int r = (I[i] - I[i+k]*B[k]);
      // cout << k << " " << i << " " << l << " " << r << endl;
      if (l < r) swap(l, r);
      S.insert({l, r});
    }
    if (best < int(S.size())) best = int(S.size()), ans = {k};
    else if (best == int(S.size())) ans.push_back(k);
  }
  cout << best << " " << ans.size() << endl; 
  for (auto t: ans) cout << t << " ";
  cout << endl;
}

C++11(clang++ 3.9) 解法, 执行用时: 610ms, 内存消耗: 11768K, 提交时间: 2020-08-26 11:42:00

#include"bits/stdc++.h"
using namespace std;

const int p=532373;
int n,a[200005],k;
unsigned long long int s[200005],s1[200005],t[200005];
set<unsigned long long int> w;
int jg,cnt;
int m;
int ans[200005];

int main()
{
	cin>>n;
	t[0]=1;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		s[i]=s[i-1]*p+a[i];
		t[i]=t[i-1]*p;
	}
	for(int i=n;i>=1;i--)
		s1[i]=s1[i+1]*p+a[i];
	for(int k=1;k<=n;k++)
	{
		w.clear();
		cnt=0;
		for(int i=k;i<=n;i+=k)
		{
			unsigned long long int x,y;
			x=s[i]-s[i-k]*t[k];
			y=s1[i-k+1]-s1[i+1]*t[k];
			//cout<<x<<' '<<y<<endl;
			if(w.count(x*y)) continue;
			w.insert(x*y);
			cnt++;
		}
		if(cnt>jg) jg=cnt,m=1,ans[m]=k;
		else if(cnt==jg) ans[++m]=k;
	}
	cout<<jg<<' '<<m<<endl;
	for(int i=1;i<=m;i++)
		cout<<ans[i]<<' ';
	cout<<endl;
	return 0;
}