← 返回题目列表

AtCoder · abc362_e

H. 计算算术子序列

中文机器翻译题面 查看原题

分数: 475 点

问题陈述

给你一个序列 A = (A_1, A_2, \dots, A_N) 长度 N。对于每个 k = 1, 2, \dots, N,求模数 998244353,(不一定是连续的)子序列 A 长度 k 是算术序列。如果两个子序列取自不同的位置,即使它们作为序列相同,它们也是可区分的。

什么是子序列? 序列的子序列 A 是通过删除零个或多个元素而获得的序列 A 并在不改变顺序的情况下排列剩余元素。

约束

  • 1 \leq N \leq 80
  • 1 \leq A_i \leq 10^9
  • 所有输入值均为整数。

输入

输入由标准输入按以下格式给出:

N
A_1 A_2 \dots A_N

输出

打印以下问题的答案 k = 1, 2, \dots, 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