[CodeForces1000]D. Yet Another Problem On a Subsequence

2018-06-28

lolifamily

DP 经典题目，枚举第一个正整数就得到了区间长度，再暴力枚举区间最后一个值， $O (n^{2})$ 的 DP 就搞定了。

在 DP 的时候，可以从 i 优化到 j 而不需要倒着循环来 DP， f[n+1] 就是答案。

注意：f[i] 的初值为 1！

D. Yet Another Problem On a Subsequence

time limit per test: 2 secondsmemory limit per test: 256 megabytesinput: standard inputoutput: standard output

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 \leq n \leq 10^{3})$ — the length of the initial sequence. The following line contains $n$ integers $a_{1}, a_{2}, \dots, a_{n} \~ (- 10^{9} \leq a_{i} \leq 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.

Examples

input

output

1
2

input

output

1
7

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

1
#include <iostream>
2
#include <cstdio>
3
#include <cstring>
4
#include <algorithm>
5
#define mod 998244353
6
using namespace std;
7
int a[1005];
8
long long C[1005][1005],f[1005];
9
int main(void)
10
{
11
  int i,j,n;
12
  scanf("%d",&n);
13
  for(i=0;i<=n;++i)C[i][0]=C[i][i]=1;
14
  for(i=1;i<=n;++i)
15
  {
16
    for(j=1;j<i;++j)C[i][j]=(C[i-1][j-1]+C[i-1][j])%mod;
17
  }
18
  for(i=1;i<=n;++i)scanf("%d",&a[i]),f[i]=1;
19
  for(i=1;i<=n;++i)
20
  {
21
    if(a[i]<=0)continue;
22
    for(j=i+a[i]+1;j<=n+1;++j)
23
    {
24
      f[j]=(f[j]+f[i]*C[j-i-1][a[i]])%mod;
25
    }
26
  }
27
  printf("%lld\n",f[n+1]);
28
  return 0;
29
}