Submission #59914541

---

Source Code Expand

#include<bits/stdc++.h>
#define fo(i,l,r) for(int i=l;i<=r;++i)
#define fd(i,r,l) for(int i=r;i>=l;--i)
#define ll long long
#define I inline int
#define V inline void
#define B inline bool
#define L inline ll
#define pi pair<int,int>
#define mk make_pair
#define fi first
#define se second
#define pb push_back
#define vi vector<int>
#define vii vector<pi>
using namespace std;
const int N=2010,mod=998244353;
char St;
I read() {
	int x=0,y=1;char c=getchar();
	while(c<48||c>57) {if(c==45)y=-y;c=getchar();}
	while(c>=48&&c<=57) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	return x*y;
}
int n,m,a[N],tot;
ll ans;
L ksm(ll x,int y) {
	ll t(1);for(;y;y>>=1,x=x*x%mod) if(y&1)t=t*x%mod;return t;
}
V check() {
	++tot;
	a[0]=m+1;
	fo(i,1,n) {
		int mx(0),mn(m+1);
		fo(j,0,i-1) mn=min(mn,a[j]);
		fo(j,i,n) mx=max(mx,a[j]);
		if(mn>mx) ans++;
	}
}
V dfs(int x) {
	if(x>n) {
		check();return ;
	}
	if(a[x]!=-1) dfs(x+1);
	else {
		fo(i,1,m) a[x]=i,dfs(x+1),a[x]=-1;
	}
}
char Ed;
int main() {
	cerr<<"memory:"<<(&St-&Ed)/1024.0<<endl;
	n=read();m=read();
	fo(i,1,n) a[i]=read();
//	dfs(1);
	a[0]=m+1;
	fo(i,1,n) {
		int las(0),mn=m+1,sl(0),mx(0),sr(0);
		fo(j,0,i-1) if(a[j]!=-1) mn=min(mn,a[j]);else sl++;
		fo(j,i,n) if(a[j]!=-1) mx=max(mx,a[j]);else sr++;
//		printf("!! %d %d %d %d\n",mn,mx,sl,sr);
		fd(j,mn,mx+1) {
			ll now=ksm(m-j+1,sl);
			ans+=(now-las)*ksm(j-1,sr)%mod;
			las=now;
		}
//		printf("%d\n",ans);
	}
	printf("%lld\n",(ans%mod+mod)%mod);
	cerr<<"time:"<<clock()<<endl;
	return 0;
}

Submission Info

Judge Result