CF1000D Yet Another Problem On a Subsequence 题解

题目链接：CF1000D Yet Another Problem On a Subsequence

题意：

如果一个数组 \([a_1,a_2,a_3,...,a_n]a_1=n-1\) 并且 \(a_1>0\) ，这个数组就被叫为好数组，如果一个序列能正好分为多个好数组，ta就被叫为好序列，现在给定一个序列，求这个序列有多少好子序列，答案对 \(998244353\) 取模。

The sequence of integers $ a_1, a_2, , 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\).

设 \(f_i\) 表示以 \(i\) 结尾的 good sequences 的数量

当 \(a_i\le 0\) 时，显然 \(f_i=0\)

当 \(a_i >0\) 时，我们可以在 \([i+a_i+1,n]\) 之间找一个good sequences拼接

然后 \([i,j]\) 之间可以随便选 \(a_i+1\) 个数，因此有 \[ f_i = \sum f_j \times \dbinom{i-j}{a_i+1} \] 时间复杂度 \(O(n^2)\)

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(2e3+15)

const int p=998244353;
int n,f[N],a[N],C[N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    C[0][0]=1;
    for(int i=1; i<=N-5; i++)
        for(int j=1; j<=i; j++)
            C[i][j]=(C[i-1][j-1]+C[i-1][j])%p;
    // for(int i=1; i<=10; i++)
    //     for(int j=1; j<=10; j++)
    //         cout << C[i][j] << " \n"[j==10];
    cin >> n;
    for(int i=1; i<=n; i++)
        cin >> a[i];
    f[n+1]=1;
    for(int i=n; i>=1; i--)
    {
        if(a[i]<=0) continue;
        for(int j=i+a[i]+1; j<=n+1; j++)
            if(a[i]+1<=j-i) f[i]=(f[i]+f[j]*C[j-i][a[i]+1]%p)%p;
    }
    int res=0;
    for(int i=1; i<=n; i++)
        res=(res+f[i])%p;
    cout << res << '\n';
    return 0;
}