English · Original
Chinese · Translation
Formal · Original
The sequence of integers $a_1, a_2, \dots, a_k$ is called a good array if $a_1 = k - 1$ and $a_1 > 0$. For example, the sequences $[3, -1, 44, 0], [1, -99]$ are good arrays, and the sequences $[3, 7, 8], [2, 5, 4, 1], [0]$ — are not.
A sequence of integers is called good if it can be divided into a positive number of good arrays. Each good array should be a subsegment of sequence and each element of the sequence should belong to exactly one array. For example, the sequences $[2, -3, 0, 1, 4]$, $[1, 2, 3, -3, -9, 4]$ are good, and the sequences $[2, -3, 0, 1]$, $[1, 2, 3, -3 -9, 4, 1]$ — are not.
For a given sequence of numbers, count the number of its **subsequences** that are good sequences, and print the number of such subsequences modulo **998244353**.
## Input
The first line contains the number $n~(1 \le n \le 10^3)$ — the length of the initial sequence. The following line contains $n$ integers $a_1, a_2, \dots, a_n~(-10^9 \le a_i \le 10^9)$ — the sequence itself.
## Output
In the single line output one integer — the number of subsequences of the original sequence that are good sequences, taken modulo **998244353**.
[samples]
## Note
In the first test case, two good subsequences — $[a_1, a_2, a_3]$ and $[a_2, a_3]$.
In the second test case, seven good subsequences — $[a_1, a_2, a_3, a_4], [a_1, a_2], [a_1, a_3], [a_1, a_4], [a_2, a_3], [a_2, a_4]$ and $[a_3, a_4]$.
整数序列 $a_1, a_2, dots.h, a_k$ 被称为好数组，当且仅当 $a_1 = k -1$ 且 $a_1 > 0$。例如，序列 $[ 3, -1, 44, 0 ]$ 和 $[ 1, -99 ]$ 是好数组，而序列 $[ 3, 7, 8 ]$、$[ 2, 5, 4, 1 ]$、$[ 0 ]$ 则不是。
一个整数序列被称为好序列，当且仅当它可以被划分为若干个（正数个）好数组。每个好数组必须是该序列的一个连续子段，且序列中的每个元素必须恰好属于一个好数组。例如，序列 $[ 2, -3, 0, 1, 4 ]$ 和 $[ 1, 2, 3, -3, -9, 4 ]$ 是好序列，而序列 $[ 2, -3, 0, 1 ]$ 和 $[ 1, 2, 3, -3 -9, 4, 1 ]$ 则不是。
对于给定的数字序列，计算其有多少个子序列是好序列，并输出该数量对 *998244353* 取模的结果。
第一行包含一个数 $n med (1 lt.eq n lt.eq 10^3)$ —— 初始序列的长度。第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n med (-10^9 lt.eq a_i lt.eq 10^9)$ —— 序列本身。
在一行中输出一个整数：原始序列中是好序列的子序列的数量，对 *998244353* 取模。
## Input
第一行包含一个数 $n med (1 lt.eq n lt.eq 10^3)$ —— 初始序列的长度。第二行包含 $n$ 个整数 $a_1, a_2, dots.h, a_n med (-10^9 lt.eq a_i lt.eq 10^9)$ —— 序列本身。
## Output
在一行中输出一个整数：原始序列中是好序列的子序列的数量，对 *998244353* 取模。
[samples]
## Note
在第一个测试用例中，有两个好子序列：$[ a_1, a_2, a_3 ]$ 和 $[ a_2, a_3 ]$。在第二个测试用例中，有七个好子序列：$[ a_1, a_2, a_3, a_4 ]$、$[ a_1, a_2 ]$、$[ a_1, a_3 ]$、$[ a_1, a_4 ]$、$[ a_2, a_3 ]$、$[ a_2, a_4 ]$ 和 $[ a_3, a_4 ]$。
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the length of the input sequence.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers, where $ a_i \in \mathbb{Z} $ for all $ i \in \{1, \dots, n\} $.
A **good array** is a nonempty subsegment $ (a_{i}, a_{i+1}, \dots, a_{i+k-1}) $ of length $ k \geq 2 $ such that:
- $ a_i = k - 1 $,
- $ a_i > 0 $.
A **good sequence** is a sequence that can be partitioned into a positive number of contiguous (non-overlapping, adjacent) good arrays, such that every element belongs to exactly one good array.
A **subsequence** of $ A $ is a sequence formed by selecting a subset of elements of $ A $ in their original order (not necessarily contiguous).
**Constraints**
1. $ 1 \leq n \leq 10^3 $
2. $ -10^9 \leq a_i \leq 10^9 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Count the number of subsequences of $ A $ that form a good sequence, modulo $ 998244353 $.
API Response (JSON)
{
"problem": {
"name": "D. Yet Another Problem On a Subsequence",
"description": {
"content": "The sequence of integers $a_1, a_2, \\dots, a_k$ is called a good array if $a_1 = k - 1$ and $a_1 > 0$. For example, the sequences $[3, -1, 44, 0], [1, -99]$ are good arrays, and the sequences $[3, ",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF1000D"
},
"statements": [
{
"statement_type": "Markdown",
"content": "The sequence of integers $a_1, a_2, \\dots, a_k$ is called a good array if $a_1 = k - 1$ and $a_1 > 0$. For example, the sequences $[3, -1, 44, 0], [1, -99]$ are good arrays, and the sequences $[3, ...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"content": "整数序列 $a_1, a_2, dots.h, a_k$ 被称为好数组，当且仅当 $a_1 = k -1$ 且 $a_1 > 0$。例如，序列 $[ 3, -1, 44, 0 ]$ 和 $[ 1, -99 ]$ 是好数组，而序列 $[ 3, 7, 8 ]$、$[ 2, 5, 4, 1 ]$、$[ 0 ]$ 则不是。\n\n一个整数序列被称为好序列，当且仅当它可以被划分为若干个（正数个）好数组。每个好数...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**Definitions** \nLet $ n \\in \\mathbb{Z}^+ $ be the length of the input sequence. \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers, where $ a_i \\in \\mathbb{Z} $ for all $ i \\in \\{1, \\dot...",
"is_translate": false,
"language": "Formal"
}
]
}