提出 #59918206

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ull unsigned long long
#define i128 __int128
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(x) (x).begin(), (x).end()
bool be;
constexpr int N = 2005, mod = 998244353;
int n, m, a[N], pre[N], pw[N][N], mn[N], mx[N];
bool en;
int main()
{
	cerr << (&be - &en) / 1024.0 / 1024 << " MB\n----------------------------" << endl;
#ifdef IAKIOI
	freopen("in.in", "r", stdin);
	// freopen("out.out", "w", stdout);
#endif
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n >> m;
	for (int i = 0; i <= 2000; ++i) {
		pw[i][0] = 1;
		for (int j = 1; j <= 2000; ++j) {
			pw[i][j] = (ll) pw[i][j - 1] * i % mod;
		}
	}
	mn[0] = m + 1;
	for (int i = 1; i <= n; ++i) {
		cin >> a[i];
		pre[i] = pre[i - 1] + (a[i] == -1);
		mn[i] = min(mn[i - 1], a[i] == -1 ? m : a[i]);
	}
	mx[n + 1] = 0;
	for (int i = n; i >= 1; --i) {
		mx[i] = max(mx[i + 1], a[i] == -1 ? 1 : a[i]);
	}
	int ans = 0;
	for (int i = 1; i <= n; ++i) {
		for (int j = mx[i]; j <= m; ++j) {
			if (j >= mn[i - 1]) continue;
			ans = (ans + (ll) (pw[j][pre[n] - pre[i - 1]] - (j == mx[i] ? 0 : pw[j - 1][pre[n] - pre[i - 1]])) * pw[m - j][pre[i - 1]]) % mod;
		}
	}
	cout << (ans + mod) % mod << endl;
	return 0;
}

提出情報

ジャッジ結果