题解：AT_arc187_b [ARC187B] Sum of CC

题目传送门。

啊。简单题。

思路

首先很容易发现连通块一定是以区间形式呈现在该序列上的，这个是容易证明的：

对于点 i,j(i<j)，若 a_i\le a_j，那么对于 \forall k\in [i,j]：

• 若 a_k\ge a_j，(i,k) 存在连边。
• 若 a_k<a_j，(k,j) 存在连边。

综上，[i,j] 每个点互相连通。

此时对于一个序列，连通块数等于分割点数量加 1（分割点指将序列分成若干个区间中间那些点）。

考虑枚举这些分割点，假设为 i，这个点能成为分割点当且仅当左边的点与右边的点之间没有连边，即 \min_{j\le i} b_j>\max_{j>i}b_j。

记 gmin_j 表示当前位置 i 左边最小值大于等于 j 的方案数，p 为 i 前面有多少个 -1，那么显然有 gmin_j=(m-j+1)^p，同理可以求出位置 i 右边最大值小于等于 j 的方案数，紧接着可以求出最大值恰好等于 j 的方案数 gmax_j，位置 i 的贡献就是 \sum_{j=2}^m gmin_j\times gmax_{j-1}。

时间复杂度 \mathcal O (nm\log n)。

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

const int Mod=998244353;
const int Maxn=2010;
int n,m;
int b[Maxn],pre[Maxn],suf[Maxn];
int pmn[Maxn],pmx[Maxn];

ll gmin[Maxn],gmax[Maxn];

inline ll ksm(ll a,int b,int mod){
    ll z=1;
    while(b){
        if(b&1) z=z*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return z;
}
ll ans;

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&b[i]);
    pmn[0]=m;
    for(int i=1;i<=n;i++){
        if(b[i]==-1) pmn[i]=pmn[i-1];
        else pmn[i]=min(pmn[i-1],b[i]);
    }
    for(int i=n;i;i--){
        if(b[i]==-1) pmx[i]=pmx[i+1];
        else pmx[i]=max(pmx[i+1],b[i]);
    }
    for(int i=1;i<=n;i++) pre[i]=pre[i-1]+(b[i]==-1);
    for(int i=n;i;i--) suf[i]=suf[i+1]+(b[i]==-1);

    for(int p=1;p<=n;p++){
        for(int j=1;j<=m;j++) gmin[j]=gmax[j]=0;
        for(int j=1;j<=pmn[p];j++) gmin[j]=ksm(m-j+1,pre[p],Mod);
        for(int j=pmx[p+1];j<=m;j++) gmax[j]=ksm(j,suf[p+1],Mod);
        for(int j=2;j<=m;j++) ans=(ans+gmin[j]*(gmax[j-1]-gmax[j-2])%Mod)%Mod;
    }
    ans=(ans+ksm(m,pre[n],Mod))%Mod;
    ans=(ans%Mod+Mod)%Mod;
    printf("%lld",ans);

    system("pause");
    return 0;
}