Submission #9190141

---

Source Code Expand

//~ while (clock()<=69*CLOCKS_PER_SEC)
//~ #pragma comment(linker, "/stack:200000000")
#ifndef LOCAL
#pragma GCC optimize("O3")
#endif
//~ #pragma GCC optimize("Ofast")
//~ #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//~ #pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ALL(x) (x).begin(), (x).end()
#define SZ(x) ((int)(x).size())
#define st first
#define nd second

using namespace __gnu_pbds;
using namespace std;
 
template <typename T>
using ordered_set =
	tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
 
#define sim template < class c
#define ris return * this
#define dor > debug & operator <<
#define eni(x) sim > typename \
  enable_if<sizeof dud<c>(0) x 1, debug&>::type operator<<(c i) {
sim > struct rge { c b, e; };
sim > rge<c> range(c i, c j) { return rge<c>{i, j}; }
sim > auto dud(c* x) -> decltype(cerr << *x, 0);
sim > char dud(...);
struct debug {
#ifdef LOCAL
~debug() { cerr << endl; }
eni(!=) cerr << boolalpha << i; ris; }
eni(==) ris << range(begin(i), end(i)); }
sim, class b dor(pair < b, c > d) {
  ris << "(" << d.first << ", " << d.second << ")";
}
sim dor(rge<c> d) {
  *this << "[";
  for (auto it = d.b; it != d.e; ++it)
	*this << ", " + 2 * (it == d.b) << *it;
  ris << "]";
}
#else
sim dor(const c&) { ris; }
#endif
};
#define imie(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
 
#define shandom_ruffle random_shuffle
 
using ll=long long;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
using vi=vector<int>;
using vll=vector<ll>;

const int MAXN = 500;
const int mod = 998244353;

int n;
int pwr2[MAXN];

struct DpRes {
	vi need, noneed;
	int width;

	DpRes(int W) : width(W) {
		need.resize(width + 2);
		noneed.resize(width + 2);
	}

	static DpRes Init() {
		DpRes res(1);
		res.need[1] = 1;
		res.noneed[0] = 1;
		return res;
	}

	DpRes Add() {
		DpRes ans(width);
		for (int bad = 0; bad <= width; ++bad) {
			const int coef = pwr2[width - bad];
			debug() << imie(bad) << imie(coef) << imie(width);
			ans.noneed[bad] = ((ll)coef * noneed[bad] + need[bad]) % mod;
			ans.need[bad] = (ll)(coef - 1) * need[bad] % mod;
		}
		return ans;
	}

	DpRes Join(const DpRes &other) {
		DpRes ans(width + other.width);
		
		for (int mybad = 0; mybad <= width; ++mybad) {
			for (int obad = 0; obad <= other.width; ++obad) {
				const int addbad = mybad + obad;
				ans.need[addbad] = (
					ans.need[addbad] +
					(ll)need[mybad] * other.need[obad] +
					(ll)noneed[mybad] * other.need[obad] +
					(ll)need[mybad] * other.noneed[obad]) % mod;
					
				ans.noneed[addbad] = (
					ans.noneed[addbad] + (ll)noneed[mybad] * other.noneed[obad]) % mod;
			}
		}
		return ans;
	}
};

int hs[MAXN];


DpRes Solve(int L, int R, int h) {
	int minh = 1e9;
	for (int i = L; i <= R; ++i) {
		minh = min(minh, hs[i]);
	}

	if (h < minh) {
		return Solve(L, R, h+1).Add();
	}

	vector<DpRes> subs;
	int start = L;
	for (int i = L; i <= R; ++i) {
		if (hs[i] == h) {
			if (start < i) {
				subs.push_back(Solve(start, i-1, h));
			}
			subs.push_back(DpRes::Init());
			start = i + 1;
		}
	}
	if (start <= R) {
		subs.push_back(Solve(start, R, h));
	}

	DpRes ans = subs[0];
	for (int i = 1; i < SZ(subs); ++i) {
		ans = ans.Join(subs[i]);
	}
	return ans;
}

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(11);
	cerr << fixed << setprecision(6);

	cin >> n;
	for (int i = 0; i < n; ++i) {
		cin >> hs[i];
	}

	pwr2[0] = 1;
	for (int i = 1; i < MAXN; ++i) {
		pwr2[i] = (pwr2[i-1] * 2) % mod;
	}

	auto ans_vec = Solve(0, n-1, 0);
	int total = 0;

	for (int i = 0; i <= n; ++i) {
		if (i % 2 == 0) {
			total = (total + ans_vec.noneed[i]) % mod;
		} else {
			total = (total + mod - ans_vec.noneed[i]) % mod;
		}
	}
	cout << total << "\n";
}

Submission Info

Judge Result