题解：AT_arc187_b [ARC187B] Sum of CC

思路历程

考虑一个给定的序列有什么简洁地计算其连边后的联通块个数的方式，初步想法是建出单调栈，输出单调栈中的元素个数，但这个东西显然不好计算（而且也很假）。然后我们发现每个后缀最大值不可能向后连边(对完了)，所以它肯定自成一个联通块，但打出代码会发现过不了样例，答案会大很多。仔细思考后会发现它会被形如 1,5,2,3 这样的数据卡掉，因为虽然后缀最大值不可能向后连边，但前面的一些点可能同时向它和它后方的点连边，使该点也被连进其他联通块。那么这是就给了我们一个启示，两个联通块分开当且仅当前者的最低点高于右边的最高点。

维护方式

考虑拆贡献，对于所以 1 \le i \le n-1 计算把 i 和 i + 1 分成两部分的方案数，对于每种方案把联通块的个数加一。最后在加上原有的联通块个数，即任意选择的方案数。 那么我们维护确定值的前缀最小值和后缀最大值，若前缀最小值大于后缀最大值，则存在分割开的方案，那么我们钦定前缀最小值，则前缀有 q 个问号，最小值为 V+1 的方案数为 (m-V)^{q}-(m-V-1)^q(因为要减去最小值大于 V+1 的方案数)，再乘上 V^{Q-q}(Q为总问号数)。注意还有一个细节，当 V+1=premin 时不需要减。所以最后的式子就是m^Q+\sum_{i=1}^{n-1} \sum_{V=sufmax}^{premin-1}((m-V)^{q}-(m-V-1)^q) \times V^{Q-q}。算这个式子时要特判 V+1=premin 。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pr;
#define fi first
#define se second
typedef double db;
#define pb push_back
#define eb emplace_back
#define bcnt __builtin_popcount
#define TS printf("!!!tiaoshi\n")
const int p=998244353;
const int N=3005;
//inline void add(int &x,int y){ (x+=y)>=p&&(x-=p);}
inline void add(int &x,int y){ x=(x+y)%p;}
inline int jia(int x,int y){ return (x+y)>=p?x+y-p:x+y; }
inline int mul(int x,int y){ return (1ll*x*y)%p;}
inline void del(int &x,int y){ (x-=y)<0&&(x+=p);}
inline int fp(int x,int y){
    if(y<0) return 0;
    int res=1;
    while(y){
        if(y&1) res=mul(res,x);
        x=mul(x,x),y>>=1;
    }
    return res;
}
int n,m,a[N],pre[N],suf[N],cnt[N];
void sol(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    pre[0]=m;
    for(int i=1;i<=n;i++){
        if(a[i]==-1) cnt[i]=cnt[i-1]+1,pre[i]=pre[i-1];
        else cnt[i]=cnt[i-1],pre[i]=min(pre[i-1],a[i]);
    }
    for(int i=n;i;i--) suf[i]=max(suf[i+1],a[i]);
    int ans=fp(m,cnt[n]);
    for(int i=1;i<n;i++){
        if(pre[i]<=suf[i+1]) continue;
        for(int j=suf[i+1];j<pre[i];j++){
            int g=1;
            if(cnt[i]){
                g=fp(m-j,cnt[i]);
                if(j+1!=pre[i]) del(g,fp(m-j-1,cnt[i]));
            }
            g=mul(g,fp(j,cnt[n]-cnt[i]));
            add(ans,g);
        }
    }
    printf("%d",ans);
}
int main(){
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout); 
    int T=1;
    //scanf("%d",&T);
    while(T--) sol(); 

    return 0;
}