Lost Array

题意翻译

## 这题是给你个数组a，长度为n，满足（k是x的长度）。当k = 3， x = {1, 2, 3}, n = 5时a如下图。  ## 让你求所有x数组的方案数和，以及每种方案的长度k（从大到小）。

题目描述

Bajtek, known for his unusual gifts, recently got an integer array $ x_0, x_1, \ldots, x_{k-1} $ . Unfortunately, after a huge array-party with his extraordinary friends, he realized that he'd lost it. After hours spent on searching for a new toy, Bajtek found on the arrays producer's website another array $ a $ of length $ n + 1 $ . As a formal description of $ a $ says, $ a_0 = 0 $ and for all other $ i $ ( $ 1 \le i \le n $ ) $ a_i = x_{(i-1)\bmod k} + a_{i-1} $ , where $ p \bmod q $ denotes the remainder of division $ p $ by $ q $ . For example, if the $ x = [1, 2, 3] $ and $ n = 5 $ , then: - $ a_0 = 0 $ , - $ a_1 = x_{0\bmod 3}+a_0=x_0+0=1 $ , - $ a_2 = x_{1\bmod 3}+a_1=x_1+1=3 $ , - $ a_3 = x_{2\bmod 3}+a_2=x_2+3=6 $ , - $ a_4 = x_{3\bmod 3}+a_3=x_0+6=7 $ , - $ a_5 = x_{4\bmod 3}+a_4=x_1+7=9 $ . So, if the $ x = [1, 2, 3] $ and $ n = 5 $ , then $ a = [0, 1, 3, 6, 7, 9] $ . Now the boy hopes that he will be able to restore $ x $ from $ a $ ! Knowing that $ 1 \le k \le n $ , help him and find all possible values of $ k $ — possible lengths of the lost array.

输入输出格式

输入格式

The first line contains exactly one integer $ n $ ( $ 1 \le n \le 1000 $ ) — the length of the array $ a $ , excluding the element $ a_0 $ . The second line contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \le a_i \le 10^6 $ ). Note that $ a_0 $ is always $ 0 $ and is not given in the input.

输出格式

The first line of the output should contain one integer $ l $ denoting the number of correct lengths of the lost array. The second line of the output should contain $ l $ integers — possible lengths of the lost array in increasing order.

输入输出样例

输入样例 #1

5
1 2 3 4 5

输出样例 #1

5
1 2 3 4 5 

输入样例 #2

5
1 3 5 6 8

输出样例 #2

2
3 5 

输入样例 #3

3
1 5 3

输出样例 #3

1
3 

说明

In the first example, any $ k $ is suitable, since $ a $ is an arithmetic progression. Possible arrays $ x $ : - $ [1] $ - $ [1, 1] $ - $ [1, 1, 1] $ - $ [1, 1, 1, 1] $ - $ [1, 1, 1, 1, 1] $ In the second example, Bajtek's array can have three or five elements. Possible arrays $ x $ : - $ [1, 2, 2] $ - $ [1, 2, 2, 1, 2] $ For example, $ k = 4 $ is bad, since it leads to $ 6 + x_0 = 8 $ and $ 0 + x_0 = 1 $ , which is an obvious contradiction. In the third example, only $ k = n $ is good. Array $ [1, 4, -2] $ satisfies the requirements. Note that $ x_i $ may be negative.