[CodeForces1000]D. Yet Another Problem On a Subsequence

2018-06-28

lolifamily

DP 经典题目，枚举第一个正整数就得到了区间长度，再暴力枚举区间最后一个值， $𝑂 (𝑛 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 $𝑎 1, 𝑎 2, \dots, 𝑎 𝑘$ is called a good array if $𝑎 1 = 𝑘 - 1$ and $𝑎 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 $𝑛\~(1≤𝑛≤103)$ — the length of the initial sequence. The following line contains $𝑛$ integers $𝑎1,𝑎2,…,𝑎𝑛\~(−109≤𝑎𝑖≤109)$ — 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 — $[𝑎 1, 𝑎 2, 𝑎 3]$ and $[𝑎 2, 𝑎 3]$ .

In the second test case, seven good subsequences — $[𝑎 1, 𝑎 2, 𝑎 3, 𝑎 4], [𝑎 1, 𝑎 2], [𝑎 1, 𝑎 3], [𝑎 1, 𝑎 4], [𝑎 2, 𝑎 3], [𝑎 2, 𝑎 4]$ and $[𝑎 3, 𝑎 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
}