ARC187B题解

题目分析

考虑一下连通块数该怎么转化。首先明确一点就是每个连通块一定包含的是编号在一定区间内的结点，也就是如果有两个点在同一连通块中，夹在它们中间的也在这一连通块中。证明可考虑反证，若存在 i,i+2 在同一连通块而 i+1 不在，则有 a_i>a_{i+1},a_i\le a_{i+2},a_{i+1}>a_{i+2}，矛盾！

也就是说我们将原序列分成了好几段，那么我们只需要在每段的左端点统计一下就可以了。现在的问题是什么情况下 i 点会新开一段。显然，如果 \exist j\in[i,n],k\in[1,i) 使得 a_j\le a_k，j 一定会向 k 连边，那么 i 显然不合法。设 a 的前缀 \min 数组为 b_i，后缀 \max 数组为 c_i，则上述条件等价于 b_{i-1}>c_i。事实上这也是充分条件，因为这样的话 i 前面的点就压根不会向 i 及之后的点连边，也就是 i 一定会新开一段。

那么我们直接维护只考虑 a_1,a_2,\cdots,a_i 时 b_i=j 的方案数 f_{i,j}，以及只考虑 a_i,a_{i+1},\cdots,a_n 时 c_i\le j 的方案数 g_{i,j}。我们统计一下 \sum\limits_{i=1}^nf_{i-1,j+1}g_{i,j} 即可。

代码实现

#include<bits/stdc++.h>
using namespace std;
const int mod=998244353;
int n,m,a[2010],f[2010][2010],g[2010][2010],ans;
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    f[0][m+1]=1;
    for(int i=1;i<=n;i++)
    {
        if(~a[i])
        {
            for(int j=1;j<=a[i];j++)
                f[i][j]=f[i-1][j];
            for(int j=a[i]+1;j<=m+1;j++)
                (f[i][a[i]]+=f[i-1][j])%=mod,f[i][j]=0;
        }
        else
        {
            int s=f[i-1][m+1];
            for(int j=m;j;j--)
            {
                f[i][j]=(1ll*f[i-1][j]*(m-j+1)+s)%mod;
                (s+=f[i-1][j])%=mod;
            }
        }
    }
    g[n+1][0]=1;
    for(int i=n;i;i--)
    {
        if(~a[i])
        {
            for(int j=a[i];j<=m;j++)
                g[i][j]=g[i+1][j];
            for(int j=0;j<a[i];j++)
                (g[i][a[i]]+=g[i+1][j])%=mod,g[i][j]=0;
        }
        else
        {
            int s=g[i+1][0];
            for(int j=1;j<=m;j++)
            {
                g[i][j]=(1ll*g[i+1][j]*j+s)%mod;
                (s+=g[i+1][j])%=mod;
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        int s=0;
        for(int j=1;j<=m;j++)
        {
            (s+=g[i][j])%=mod;
            (ans+=1ll*f[i-1][j+1]*s%mod)%=mod;
        }
    }
    printf("%d",ans);
    return 0;
}