Count Arithmetic Subsequences

题目描述

你被给定一个长度为 $N$ 的序列 $A = (A_1, A_2, \dots, A_N)$。对于每个 $k = 1, 2, \dots, N$，求长度为 $k$ 的（不一定连续的）$A$ 的子序列中为等差数列的个数，对 $998244353$ 取模。若两个子序列取自不同的位置，即使作为序列相同，也视为不同。

输入格式

输入按下述格式从标准输入给出： $N$ $A_1$ $A_2$ $\dots$ $A_N$

输出格式

按 $k = 1, 2, \dots, N$ 的顺序输出答案，单行，空格分隔。

5
1 2 3 2 3

5 10 3 0 0

4
1 2 3 4

4 6 2 1

1
100

1

提示

$1 \leq N \leq 80$ $1 \leq A_i \leq 10^9$ 所有输入值均为整数。长度为 $1$ 的子序列有 $5$ 个，全部为等差数列。 长度为 $2$ 的子序列有 $10$ 个，全部为等差数列。 长度为 $3$ 的等差子序列有 $3$ 个：$(A_1, A_2, A_3)$、$(A_1, A_2, A_5)$ 和 $(A_1, A_4, A_5)$。 不存在长度为 $4$ 或更长的等差子序列。

标签: AtCoder|abc362E

来源

AtCoder|abc362E