LOJ#2427. 「POI2010」珍珠项链 Beads

题目地址

题目链接

题解

不会算复杂度真是致命，暴力枚举k每次计算是n/2+n/3+n/4+...+1的，用调和级数算是(O(nlogn))的...

如果写哈希表的话能够(O(nlogn))，或者直接拿个set存就(O(nlognlogn))。

进制要选好，233不能过，2333过的点会多一点，然后选13131才过了

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <set>
typedef unsigned long long ull;
const int N = 200010;
const ull base = 13131;
using namespace std;

int Ans, n, a[N], ans[N], cnt = 0;
ull h1[N], h2[N], p[N];
set<ull> st;

ull cal1(int l, int r) { return h1[r] - h1[l - 1] * p[r - l + 1]; }

ull cal2(int l, int r) { return h2[l] - h2[r + 1] * p[r - l + 1]; }

int ins(int x) {
	st.clear();
	for(int l = 1; l + x - 1 <= n; l += x) {
		int r = l + x - 1;
		ull ha = min(cal1(l, r), cal2(l, r));
		st.insert(ha);
	}
	return (int)st.size();
}

int main() {
	scanf("%d", &n); p[0] = 1;
	for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
	for(int i = 1; i <= n; ++i) h1[i] = h1[i - 1] * base + a[i], p[i] = p[i - 1] * base;
	for(int i = n; i; i--) h2[i] = h2[i + 1] * base + a[i];
	for(int i = 1; i <= n; ++i) {
		int num = ins(i);
		if(num > Ans) { Ans = num; cnt = 0; }
		if(num == Ans) ans[++cnt] = i;
	}
	printf("%d %d
", Ans, cnt);
	for(int i = 1; i <= cnt; ++i) printf("%d ", ans[i]);
	return 0;
}