Two Frogs

题目描述

In the Lonely Mountain, there are a lot of treasure well protected by dwarfs. Later, one day, the last dragon Smaug came and sensed the treasure being. As known to all, dragons are always much too greedy for treasure. So definitely, the war between dwarfs and Smaug begins.

During the war, two goblins Alice and Bob are turned into frogs by Gandalf, The Grey. In front of them, there are nn lotus leaves in a line. In order to break the spell, they must jump from the $11$ - st lotus leaf to the nn-th lotus leaf. If the frog is now on the ii-th lotus leaf instead of the $nn$ - th lotus leaf, it can jump to a lotus leaf in range $(i,i+a_i](i,\; i\; +\; a\_i]$ .

Goblins are lack of intelligence and it's also true even after turned into frogs. So Alice and Bob will jump randomly, which means, they will separately pick an available lotus leaf in every jump uniformly at random.

Since Alice and Bob have already being playing games for decades, so they want to know the probability that they jump to the $nn$ - th lotus leaf with the same count of jumps.

输入描述

The first line contains an integer $n(2\le n\le 8000)n\; (2\; \backslash leq\; n\; \backslash leq\; 8\backslash ,000)$, denoting the number of lotus leaf.

The second line contains $n\mathrm{-}1n-1$ integers $a_1,a_2,\dots ,a_{n-1}a\_1,\; a\_2,\; \backslash ldots,\; a\_\{n-1\}$ , where the $ii$ - th integer $a_i(1\le a_i\le n-i)a\_i\; (1\; \backslash leq\; a\_i\; \backslash leq\; n-i)$ indicates the range of lotus leaves that can be reached from the ii-th lotus leaf.

输出描述

Output a line containing a single integer, indicating the probability that Alive and Bob jump to nn-th lotus leaf with the same count of jumps, taken modulo $998244353998\backslash ,244\backslash ,353$.

Formally speaking, let the result, which is a rational number, be $\frac{x}{y}\backslash frac\{x\}\{y\}$ as an irreducible fraction, you need to output $x\cdot y^{-1}\mathrm{m}\mathrm{o}\mathrm{d}998244353x\; \backslash cdot\; y^\{-1\}\; \backslash bmod\{998\backslash ,244\backslash ,353\}$ , where $y^{-1}y^\{-1\}$ is a number such that $y\cdot y^{-1}\equiv 1(\mathrm{m}\mathrm{o}\mathrm{d}998244353)y\; \backslash cdot\; y^\{-1\}\; \backslash equiv\; 1\; \backslash pmod\{998\backslash ,244\backslash ,353\}$. You may safely assume that such $y^{-1}y^\{-1\}$ always exists.

输入样例1：

输出样例1：

#include<bits/stdc++.h>
using namespace std;
#define __T int csT;scanf("%d",&csT);while(csT--)
#define endl '\n'
#define int long long
const int mod=998244353;
const double PI= acos(-1);
const double eps=1e-6;
const int N=2e5+7;

int n;
long long ans,sum;
long long dp[8003][8003],cf[8003];
long long a[8003],inv[8003];
void get_inv()
{
    inv[1]=1;
    for(int i=2;i<=n;i++)
    {
        inv[i]=(mod-mod/i)*inv[mod%i]%mod;
    }
}//线性求逆元
inline void sol()
{
    scanf("%lld",&n);
    get_inv();
    for(int i=1;i<n;++i)scanf("%lld",&a[i]);
    dp[0][1]=1;
    for(int i=1;i<n;++i)
    {
        for(int j=i;j<n;++j)
        {
            cf[j+1]=(cf[j+1]+dp[i-1][j]*inv[a[j]]%mod)%mod;
            cf[j+a[j]+1]=(cf[j+a[j]+1]-dp[i-1][j]*inv[a[j]]%mod+mod)%mod;
        }
        sum=0;
        for(int j=1;j<=n;++j)
        {
            sum=(sum+cf[j])%mod;
            cf[j]=0;
            dp[i][j]=sum;
            //printf("%d %d %lld\n",i,j,dp[i][j]);
        }
    }
    ans=0;
    for(int i=1;i<n;++i)ans=(ans+dp[i][n]*dp[i][n]%mod)%mod;
    printf("%lld\n",ans);
}
signed main()
{
    //__T
    sol();
    return 0;
}