증가하는 부분 수열의 개수

면접 대비

시간 제한2초메모리 제한1024 MB

요약

각 위치 i에 대해 A_i로 끝나는 증가 부분 수열의 개수를 998244353으로 나눈 나머지로 구한다.

문제

길이가 $N$ 인 수열 $A$ 가 주어진다. 각 $i$ 에 대해, $A_i$ 로 끝나는 증가하는 부분 수열의 개수를 구하자.

답이 매우 커질 수 있으므로 $998\,244\,353$ 으로 나눈 나머지를 출력한다.

증가하는 부분 수열이 무엇인지 잘 모르는 사람을 위해 동원이가 아래 정의를 준비했다.

부분 수열이란 주어진 수열에서 1개 이상의 원소를 골라 원래 순서대로 나열하여 얻은 수열을 말한다.
증가하는 부분 수열이란 맨 처음 원소를 제외한 모든 원소가 바로 전 원소보다 큰 수열을 말한다. 다시 말해 길이가 $N$ 인 부분 수열 $A$ 가 있을 때, $A_{i-1} < A_i$ ( $2 \le i \le N$ )를 만족하면 $A$ 는 증가하는 부분 수열이다.

동원이는 위 정의에 따라 길이가 1인 부분 수열은 항상 증가하는 부분 수열이라는 점에 주의하라고 덧붙였다.

첫째 줄에 수열의 길이 $N$ 이 주어진다.

둘째 줄에 $N$ 개의 정수 $A_1, A_2, \cdots, A_N$ 이 공백으로 구분되어 주어진다.

첫 번째 줄에 $N$ 개의 정수를 출력한다.

$i$ 번째로 출력하는 수는 $A_i$ 로 끝나는 증가하는 부분 수열의 개수를 $998\,244\,353$ 으로 나눈 나머지이다.