dp - 求符合题意的序列的个数

The sequence of integers a1,a2,…,ak is called a good array if a1=k−1 and a1>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≤n≤103)

— the length of the initial sequence. The following line contains n integers a1,a2,…,an (−109≤ai≤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

3
2 1 1

Output

Input

4
1 1 1 1

Output

Note

In the first test case, two good subsequences — [a1,a2,a3]

and [a2,a3]

In the second test case, seven good subsequences — [a1,a2,a3,a4],[a1,a2],[a1,a3],[a1,a4],[a2,a3],[a2,a4]

and [a3,a4].

题意：给你一串数字，并按照题目叙述，给出一个好序列的定义，并且任意个好序列之间可以合并起来，问最终好序列的个数。

思路分析：

　　dp[i] 表示以i位置开始的序列的最优解，倒着推一下就可以了， dp[i] += dp[j-i][i]*dp[j+1] (i+a[i] <= j <= n)

代码示例：

ll n;

ll a[1005];

ll c[1005][1005];

void init(){

    for(ll i = 1; i <= 1000; i++){

        c[i][0] = c[i][i] = 1;

        for(ll j = 1; j < i; j++){

            c[i][j] = (c[i-1][j]+c[i-1][j-1])%mod;

        }

    }

}

ll dp[1005];

int main() {

    //freopen("in.txt", "r", stdin);

    //freopen("out.txt", "w", stdout);

    init();

    cin >> n;

    for(ll i = 1; i <= n; i++){

        scanf("%lld", &a[i]);

    }

    dp[n+1] = 1;

    ll ans = 0;

    for(ll i = n-1; i >= 1; i--){

        ll p = i+a[i];

        if (a[i] <= 0) continue;

        for(ll j = p; j <= n; j++){

            dp[i] += (c[j-i][a[i]]*dp[j+1])%mod;

            dp[i] %= mod;

        }

        ans += dp[i];

        ans %= mod;

    }

    printf("%lld\n", ans);

    return 0;

}

巴特西

dp - 求符合题意的序列的个数

最新文章

热门文章