[AdditionalFile2427.zip](file://AdditionalFile2427.zip?type=additional_file)

P3498 [POI 2010] KOR-Beads

题目描述

Byteasar 有 $n$ 个珠子，第 $i$ 个颜色为 $a_i$，和一台机器。

Byteasar 可以选定一个值 $k$，然后机器会让 $1\sim k$ 的珠子组成项链 $b_1$，$k+1\sim 2k$ 的珠子组成项链 $b_2$，以此类推，最后 $n\bmod k$ 个珠子不会组成项链，而是被丢弃。

现在让你求出一个 $k$ 值，使得在 $\left\lfloor\dfrac{n}{k}\right\rfloor$ 个项链 $b$ 中，存在 不同的 项链数量最多。

项链可以反转，形式化地，$b_x$ 和 $b_y$ 不同，当且仅当存在至少一个 $i$，使得 $b_{x,i}\ne b_{y,i}$ 且 $b_{x,i} \ne b_{y,k-i+1}$。

例如 $[1,2,3]$ 和 $[3,2,1]$ 是相同的，而 $[1,2,3]$ 和 $[2,3,1]$ 是不同的。

输入格式

输入两行，第一行为 $n$。

第二行为 $n$ 个正整数，第 $i$ 个正整数代表 $a_i$。

输出格式

输出两行。

第一行两个整数，分别代表不同的项链最多的数量，以及不同的项链最多时，$k$ 的个数。

第二行若干个整数，代表所有能使不同的项链最多的 $k$ 值，这可以按任意顺序输出。

【样例解释】

$a$ 为 $[1,1,1,2,2,2,3,3,3,1,2,3,3,1,2,2,1,3,3,2,1]$。

• $k=1$ 的时候，我们得到 $3$ 个不同的项链 $b$：$[1],[2],[3]$。
• $k=2$ 的时候，我们得到 $6$ 个不同的项链：$[1,1],[1,2],[2,2],[2,3],[3,3],[3,1]$。
• $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]$。

输入输出样例 #1

输入 #1

21
1 1 1 2 2 2 3 3 3 1 2 3 3 1 2 2 1 3 3 2 1

输出 #1

6 1
2

说明/提示

对于全部数据，$1\le n\le2\times 10^5$，且 $\forall 1\le i\le n$，有 $1\le a_i\le n$。

#2427. 「POI2010」珍珠项链 Beads

标签: 传统 | 时间限制: 2000 ms | 内存限制: 64 MiB |

题目描述

译自 POI 2010 Stage 1.「Beads」

Byteasar 决定制造一条项链，她买了一串珠子，她有一个机器，能把这条珠子切成很多段，使得每段恰有 $k$ 个珠子 $(k>0)$ ，如果这条珠子的长度不是 $k$ 的倍数，最后一块长度小于 $k$ 的段就被丢弃了。
Byteasar 想知道，选择什么数字 $k$ 可以得到最多的不同的段。注意这里的段是可以反转的，即，子串 $1,2,3$ 和 $3,2,1$ 被认为是一样的。

输入格式

第一行一个正整数 $n$ ，表示珠子的长度。
第二行 $n$ 个空格隔开的正整数 $a_1,a_2,\cdots a_n$ ，描述这一串珠子的颜色。

输出格式

第一行两个空格隔开的正整数，第一个表示能获得的最大不同的段的个数，第二个表示能获得最大值的 $k$ 的个数。
第二行若干空格隔开的正整数 $k$ ，表示所有能够取得最大值的 $k$ ，请将 $k$ 按照从小到大的顺序输出。

样例

输入

21
1 1 1 2 2 2 3 3 3 1 2 3 3 1 2 2 1 3 3 2 1

输出

6 1
2

数据范围与提示

对于 $100\%$ 的数据， $1\le n\le 2\times 10^5$ ，且 $\forall 1\le i\le n$ ，有 $1\le a_i\le n$ 。

Translated By diamond_duke