일본 지식

시간 제한10초메모리 제한512 MB

요약

각 k마다 x_i가 A_i 이하인 비감소 수열 중 x_i가 A_i와 같은 위치가 정확히 k개인 수열의 개수를 998244353으로 나눈 나머지를 구합니다.

난이도: 어려움10점 중 9점
유형: 동적 계획법, 분할 정복, 조합론, 수학
정답자: 아직 제출이 없습니다

문제

이 문제는 일부 나라에서는 널리 알려져 있을지 모르지만, 아무도 이런 문제를 내지 않는다면 다른 나라는 이런 문제를 어떻게 배울까?

길이가 $N$ 인 비감소 양의 정수 수열 $A = (A\_1, A\_2, \ldots, A\_N)$ 이 주어진다. 각 $k=0,1,2,\ldots,N$ 에 대해, 다음 조건을 모두 만족하는 길이 $N$ 의 비감소 음이 아닌 정수 수열 $x = (x\_1, x\_2, \ldots, x\_N)$ 의 개수를 $998244353$ 으로 나눈 나머지로 구하라.

모든 $1 \leq i \leq N$ 에 대해 $x\_i \leq A\_i$ 이다.
$x\_i=A\_i$ 를 만족하는 인덱스 $i$ 의 개수가 정확히 $k$ 개이다.

입력

첫째 줄에 정수 $N$ ( $1 \leq N \leq 250000$ )이 주어진다.

둘째 줄에 정수 $A\_1,A\_2,\ldots,A\_N$ ( $1 \leq A\_1 \leq A\_2 \leq \cdots \leq A\_N \leq 250000$ )이 주어진다.

출력

각 $k=0,1,2,\ldots,N$ 에 대해 답을 출력한다.

예제3

예제 1
입력
```
3
1 2 3
```
예상 출력
```
5 5 3 1
```
예제 2
입력
```
4
3 3 3 3
```
예상 출력
```
15 10 6 3 1
```
예제 3
입력
```
5
10 10 11 11 12
```
예상 출력
```
3982 1285 352 77 12 1
```