Yet Another Problem On a Subsequence (Codeforces 1000D)
Tags: DP, combinatorics

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.

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]$$$.

Sample Inputs:
3
2 1 1

4
1 1 1 1

Sample Outputs:
2

7

Solution (Python):
from sys import stdin, stdout
get_string = lambda : stdin.readline().strip('\n')
get_intmap = lambda : map(int, get_string().split(' '))

def ncr_generator(n, r):
    ncrr = 1
    while True:
        yield ncrr
        n += 1
        ncrr = ncrr * n // (n - r)

def testcase():
    n = int(input())
    a = tuple(get_intmap())
    m = 998244353
    dp = [0] * (n + 1)
    dp[n] = 1
    for i in range(n - 1, -1, -1):
        ai = a[i]
        if ai <= 0:
            continue
        for (j, ncrr) in zip(range(i + ai + 1, n + 1), ncr_generator(ai, ai)):
            dp[i] = (dp[i] + ncrr * dp[j]) % m
    ans = 0
    for i in dp[:-1]:
        ans = (ans + i) % m
    print(ans)
testcase()

Solution (Python):
n = int(input())
m = 998244353
dp = [1] + [0] * n
for i in map(int, input().split()):
    v = dp[:]
    if 0 < i < n:
        v[i] = (v[i] + v[0]) % m
    for j in range(n):
        v[j] = (v[j] + dp[j + 1]) % m
    dp = v
print((dp[0] - 1) % m)

Solution (Python):
n = int(input())
m = 998244353
dp = [1] + [0] * n
for j in map(int, input().split()):
    v = dp[:]
    if 0 < j < n:
        v[j] = (v[j] + v[0]) % m
    for k in range(n):
        v[k] = (v[k] + dp[k + 1]) % m
    dp = v
print((dp[0] - 1) % m)