103624: [Atcoder]ABC362 E - Count Arithmetic Subsequences

Problem Statement

You are given a sequence $A = (A_1, A_2, \dots, A_N)$ of length $N$. For each $k = 1, 2, \dots, N$, find the number, modulo $998244353$, of (not necessarily contiguous) subsequences of $A$ of length $k$ that are arithmetic sequences. Two subsequences are distinguished if they are taken from different positions, even if they are equal as sequences.

Constraints

• $1 \leq N \leq 80$
• $1 \leq A_i \leq 10^9$
• All input values are integers.

Input

The input is given from Standard Input in the following format:

$N$
$A_1$ $A_2$ $\dots$ $A_N$

Output

Print the answers for $k = 1, 2, \dots, N$ in this order, in a single line, separated by spaces.

Sample Input 1

5
1 2 3 2 3

Sample Output 1

5 10 3 0 0

• There are $5$ subsequences of length $1$, all of which are arithmetic sequences.
• There are $10$ subsequences of length $2$, all of which are arithmetic sequences.
• There are $3$ subsequences of length $3$ that are arithmetic sequences: $(A_1, A_2, A_3)$, $(A_1, A_2, A_5)$, and $(A_1, A_4, A_5)$.
• There are no arithmetic subsequences of length $4$ or more.

Sample Input 2

4
1 2 3 4

Sample Output 2

4 6 2 1

Sample Input 3

1
100

Sample Output 3

1

问题陈述

给定一个长度为N的序列A = (A_1, A_2, …, A_N)。对于每个k = 1, 2, …, N，找出模998244353的（不一定是连续的）子序列的数量，这些子序列是长度为k的等差数列。如果两个子序列来自不同的位置，即使它们作为序列是相等的，也将它们区分开来。

约束条件

• 1 ≤ N ≤ 80
• 1 ≤ A_i ≤ 10^9
• 所有输入值都是整数。

输入

输入从标准输入以下格式给出：

N
A_1 A_2 … A_N

输出

按顺序打印k = 1, 2, …, N的答案，在一行中，用空格分隔。

示例输入1

5
1 2 3 2 3

示例输出1

5 10 3 0 0

• 有5个长度为1的子序列，它们都是等差数列。
• 有10个长度为2的子序列，它们都是等差数列。
• 有3个长度为3的等差数列子序列：(A_1, A_2, A_3)，(A_1, A_2, A_5)，和(A_1, A_4, A_5)。
• 没有长度为4或更长的等差数列子序列。

示例输入2

4
1 2 3 4

示例输出2

4 6 2 1

示例输入3

1
100

示例输出3

1