Description
Zxl有一次决定制造一条项链，她以非常便宜的价格买了一长条鲜艳的珊瑚珠子，她现在也有一个机器，能把这条珠子切成很多块（子串），每块有k（k>0）个珠子，如果这条珠子的长度不是k的倍数，最后一块小于k的就不要拉（nc真浪费），保证珠子的长度为正整数。 Zxl喜欢多样的项链，为她应该怎样选择数字k来尽可能得到更多的不同的子串感到好奇，子串都是可以反转的，换句话说，子串（1，2，3）和（3,2,1）是一样的。写一个程序，为Zxl决定最适合的k从而获得最多不同的子串。 例如：这一串珠子是： (1,1,1,2,2,2,3,3,3,1,2,3,3,1,2,2,1,3,3,2,1)， k=1的时候，我们得到3个不同的子串： (1),(2),(3) k=2的时候，我们得到6个不同的子串： (1,1),(1,2),(2,2),(3,3),(3,1),(2,3) k=3的时候，我们得到5个不同的子串： (1,1,1),(2,2,2),(3,3,3),(1,2,3),(3,1,2) k=4的时候，我们得到5个不同的子串： (1,1,1,2),(2,2,3,3),(3,1,2,3),(3,1,2,2),(1,3,3,2)
共有两行，第一行一个整数n代表珠子的长度，（），第二行是由空格分开的颜色ai（1<=ai<=n）。
Output
也有两行，第一行两个整数，第一个整数代表能获得的最大不同的子串个数，第二个整数代表能获得最大值的k的个数，第二行输出所有的k（中间有空格）。
21
1 1 1 2 2 2 3 3 3 1 2 3 3 1 2 2 1 3 3 2 1
Sample Output
6 1
2
Solution
枚举起点，枚举子串长度，哈希判重。话说哈希可以不取模，直接unsigned long long让他自然溢出。
调和级数分析一下这个东西，复杂度\(N* \sum _{i=1}^N \frac{1}{i} \)，是logN的。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
| #include <cstdio>
#include <algorithm>
#include <set>
#include <vector>
using namespace std;
typedef unsigned long long ULL;
const int INF = 1009999999;
int getint() {
int r = 0, k = 1; char c = getchar();
for (; '0' > c || c > '9'; c = getchar()) if (c == '-') k = -1;
for (; '0' <= c && c <= '9'; c = getchar()) r = r * 10 - '0' + c;
return r * k;
}
set<ULL> S;
vector<int> V;
ULL H[1000005], T[1000005], H2[1000005];
int A[1000005];
int n;
ULL GetHash1(int l, int r) {
return H[r] - H[l-1] * T[r - l + 1];
}
ULL GetHash2(int r, int l) {
return H2[l] - H2[r+1] * T[r - l + 1];
}
int main() {
n = getint();
T[0] = 1;
for (int i = 1; i <= n; ++i) {
A[i] = getint();
H[i] = H[i-1] * n + A[i];
T[i] = T[i-1] * n;
}
for (int i = n; i; --i) {
H2[i] = H2[i+1] * n + A[i];
}
ULL ind;
int mx = 0;
for (int k = 1; k <= n; ++k) {
int cnt = 0;
S.clear();
for (int i = 1; i + k - 1 <= n; i += k) {
ind = GetHash1(i, i + k - 1) * GetHash2(i + k - 1, i);
if (S.find(ind) == S.end()) {
++cnt;
S.insert(ind);
}
}
if (mx < cnt) {
mx = cnt;
V.clear();
V.push_back(k);
} else {
if (mx == cnt) {
V.push_back(k);
}
}
}
printf("%d %lu\n", mx, V.size());
printf("%d", V[0]);
for (int i = 1; i < V.size(); ++i)
printf(" %d", V[i]);
return 0;
}
|