#P3498. [POI 2010] KOR-Beads

    ID: 4339 远端评测题 1000ms 125MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>2010POI(波兰)Special Judge枚举哈希 hashing

[POI 2010] KOR-Beads

题目描述

Byteasar once decided to start manufacturing necklaces.

He subsequently bought a very long string of colourful coral beads for a bargain price.

Byteasar now also has a machine that, for a given (), can cut the string into pieces (or substrings) of coral beads (i.e., the first piece consists of the beads no.

, the second of , etc.).

If the length of the string (measured in coral beads) is not a multiple of , then the last piece is not used, as it has length smaller than .

From now on we denote the colours of the beads with positive integers.

Byteasar, always praising diversity, wonders how he should choose the number in order to get as many different substrings as possible.

The ends of the long string that will be cut are different: there are specific beginning and ending (rather than two interchangeable endpoints), and the machine of course starts cutting at the beginning. On the other hand, in the substrings obtained from cutting the endpoints are interchangeable, and so the substrings can be reversed. In other words, the substrings and are identical to us. Write a program that determines the optimum value of for Byteasar.

输入格式

In the first line of the standard input there is an integer () denoting the length of the string to cut.

In the second line there are positive integers (), separated by single spaces, that denote the colours of successive beads in Byteasar's string.

输出格式

Two integers, separated by a single space, should be printed out to the first line of the standard ouput:

the (maximum) number of different substrings that can be obtained with an optimal choice of parameter , and the number of such optimal values of .

The second line should contain integers separated by single spaces:

the values of parameter that yield an optimum solution; these can be given in arbitrary order.

输出两行,第一行第一个数为最多可以得到的不同子串的个数,第二个数为取到最优解时的不同的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

提示

1n2×1051≤n≤2\times 10^5,且 1in\forall 1\le i\le n,有 1ain1\le a_i\le n