CF – 1000 – D Yet Another Problem On a Subsequence(DP+某快速计算阶乘的逆元）

题目链接：https://codeforces.com/contest/1000/problem/D
题目大意：对于一个序列，首元素等于序列长度-1且大于0的话，就认为这个序列是一个好的序列，若干个好的序列组合在一起也是一个好的序列，给出一个序列问一共可以从中找到多少个好的子序列。
解题思路：我们可以快速的算出以第i个元素为首元素的好序列有多少个，就是从后面的n-i个元素中取a[i]个的方案数，高中排列组合走起。
但是如果用暴力的方法计算阶乘相除的话即会超时也会爆longlong，所以要用到这个快速计算阶乘的逆元来帮忙。
还有就是题目中说了多个好序列组合到一起也是一个好的序列，所以要用到DP,dp[i]代表以i元素及之后的元素为首元素所能组成的好序列的个数，这样从后向前推就可以了。
代码

#include <iostream>
#include <bits/stdc++.h>
#define ll long long
using namespace std;

const int M=998244353;
const int N=2000;

ll dp[N],sum[N];
ll a[N];
ll fac[N]={1,1},inv[N]={1,1},f[N]={1,1};

ll C(ll a,ll b)//求组合数
{
    if(b>a)return 0;
    return fac[a]*inv[b]%M*inv[a-b]%M;
}

void init()//某快速计算阶乘的逆元
{
    for(int i=2;i<N;i++)
    {
        fac[i]=fac[i-1]*i%M;//阶乘
        f[i]=(M-M/i)*f[M%i]%M;
        inv[i]=inv[i-1]*f[i]%M;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    init();
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    dp[n+1]=1;
    for(ll i=n;i>=1;i--)
    {
        if(a[i]<=0)
        {
            dp[i]=0;
            continue;
        }
        for(ll j=i;j<=n+1;j++)
        {
            dp[i]+=C(j-i-1,a[i])*dp[j];
            dp[i]%=M;
        }
    }
    ll ans=0;
    for(ll i=1;i<=n;i++)
    {
        ans+=dp[i];
        ans%=M;
    }
    cout<<ans<<endl;
    return 0;
}