AT_abc362_e.[ABC362E] Count Arithmetic Subsequences

普及+/提高

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 $N$ 的数列 $A=(A_1,A_2,\dots,A_N)$ 。对于每个 $k=1,2,\dots,N$ ，请你求出 $A$ 的所有长度为 $k$ 的（不一定连续的）等差子序列的个数，并对 $998244353$ 取模。注意，如果两个子序列的选取位置不同，即使它们的数值序列相同，也视为不同的子序列。

子序列指的是从数列 $A$ 中删除 $0$ 个或多个元素后，保留剩下元素原有顺序得到的数列。

输入格式

输入从标准输入中给出，格式如下：

$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
```
输入#2
```
4
1 2 3 4
```
输出#2
```
4 6 2 1
```
输入#3
```
1
100
```
输出#3
```
1
```

说明/提示

限制条件

$1 \leq N \leq 80$
$1 \leq A_i \leq 10^9$
输入均为整数

样例解释 1

长度为 $1$ 的子序列共有 $5$ 个，这些都是长度为 $1$ 的等差数列。
长度为 $2$ 的子序列共有 $10$ 个，这些都是长度为 $2$ 的等差数列。
长度为 $3$ 的等差子序列有 $3$ 个，分别是 $(A_1,A_2,A_3),(A_1,A_2,A_5),(A_1,A_4,A_5)$ 。
长度为 $4$ 及以上的等差子序列不存在。

由 ChatGPT 4.1 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页