Language: C++

#include <algorithm>
#include <cassert>
#include <iostream>
#include <numeric>
#include <set>
#include <vector>
using namespace std;

template<uint32_t mod> class modulo_int {
  class dummy_type { };

  modulo_int &normalize2() {
    if (value >= mod) value -= mod;
    return *this;
  }

  modulo_int(const uint32_t value, const dummy_type &) : value(value) {}

public:
  explicit modulo_int(const int64_t value = 0) : value(value % mod + mod) { normalize2(); }

  uint32_t get() const { return value; }

  modulo_int operator+() const {
    return *this;
  }
  modulo_int operator-() const {
    return modulo_int(mod - this->value, {}).normalize2();
  }
  modulo_int operator+(const modulo_int &that) const {
    return modulo_int(this->value + that.value, {}).normalize2();
  }
  modulo_int operator-(const modulo_int &that) const {
    return modulo_int(this->value + (mod - that.value), {}).normalize2();
  }
  modulo_int operator*(const modulo_int &that) const {
    return modulo_int(((uint64_t)(this->value) * that.value) % mod, {});
  }
  // mod should be prime
  modulo_int operator/(const modulo_int &that) const {
    return *this * that.inv();
  }
  friend modulo_int pow(const modulo_int base, uint64_t e) {
    if (e == 0) return modulo_int(1, {});
    if (e == 1) return base;
    auto tmp = pow(base * base, e / 2);
    return (e&1) ? tmp * base : tmp;
  }

  modulo_int &operator+=(const modulo_int &that) { return *this = *this + that; }
  modulo_int &operator-=(const modulo_int &that) { return *this = *this - that; }
  modulo_int &operator*=(const modulo_int &that) { return *this = *this * that; }
  modulo_int &operator/=(const modulo_int &that) { return *this = *this / that; }

  modulo_int inv() const {
    pow(*this, mod - 2);
  }

private:
  uint32_t value;
};

using mod_t = modulo_int<1000000007>;

// pair(stripe case, non-stripe case)
pair<mod_t, mod_t> solve_rec(
    const vector<int> &h,
    const int l,
    const int r,
    const int current_h
)
{
  assert(r > l);
  const int new_h = *min_element(begin(h) + l, begin(h) + r);
  assert(new_h > current_h);
  if (new_h == *max_element(begin(h) + l, begin(h) + r)) {
    mod_t stripe_res = pow(mod_t(2), h[l] - current_h);
    mod_t nonstripe_res = pow(mod_t(2), r - l) - mod_t(2);    // -2 for stripe
    return make_pair(stripe_res, nonstripe_res);
  }
  vector<int> ls, rs;
  for (int i = l; i < r; ++i) {
    if (new_h == h[i]) continue;
    if (rs.empty() || rs.back() != i) {
      ls.push_back(i);
      rs.push_back(i+1);
    } else {
      ++rs.back();
    }
  }
  assert(ls.size() == rs.size());
  assert(!ls.empty());

  mod_t nonstripe_res(1);
  mod_t stripe_res(1);
  const int t = ls.size();
  vector<mod_t> stripe, nonstripe;
  for (int i = 0; i < t; ++i) {
    mod_t stripe, nonstripe;
    tie(stripe, nonstripe) = solve_rec(h, ls[i], rs[i], new_h);
    nonstripe_res *= nonstripe + (stripe * mod_t(2));
    stripe_res *= stripe;
  }
  for (int i = l; i < r; ++i) if (h[i] == new_h) nonstripe_res *= mod_t(2);
  nonstripe_res -= stripe_res * mod_t(2);
  stripe_res *= pow(mod_t(2), new_h - current_h);
  return make_pair(stripe_res, nonstripe_res);
}


int main() {
  int n;
  cin >> n;
  vector<int> h(n);
  for (auto &x : h) cin >> x;
  if (n == 1) {
    cout << pow(mod_t(2), h[0]).get() << endl;
    return 0;
  }
  mod_t precompute(1);
  for (int i = 0; i < n; ++i) {
    const int adj = max(i == 0 ? 0 : h[i-1], i == n-1 ? 0 : h[i+1]);
    if (adj < h[i]) {
      precompute *= pow(mod_t(2), h[i] - adj);
      h[i] = adj;
    }
  }
  mod_t stripe, nonstripe;
  tie(stripe, nonstripe) = solve_rec(h, 0, n, 0);

  cout << (precompute * (stripe + nonstripe)).get() << endl;
  return 0;
}


Compiler output:
a.cc:9:10: error: 'uint32_t' has not been declared
    9 | template<uint32_t mod> class modulo_int {
      |          ^~~~~~~~
a.cc:17:20: error: 'uint32_t' does not name a type
   17 |   modulo_int(const uint32_t value, const dummy_type &) : value(value) {}
      |                    ^~~~~~~~
a.cc:7:1: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
    6 | #include <vector>
  +++ |+#include <cstdint>
    7 | using namespace std;
a.cc:22:3: error: 'uint32_t' does not name a type
   22 |   uint32_t get() const { return value; }
      |   ^~~~~~~~
a.cc:22:3: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
a.cc:43:48: error: 'uint64_t' has not been declared
   43 |   friend modulo_int pow(const modulo_int base, uint64_t e) {
      |                                                ^~~~~~~~
a.cc:60:3: error: 'uint32_t' does not name a type
   60 |   uint32_t value;
      |   ^~~~~~~~
a.cc:60:3: note: 'uint32_t' is defined in header '<cstdint>'; this is probably fixable by adding '#include <cstdint>'
a.cc:66:6: error: 'mod_t' was not declared in this scope; did you mean 'mode_t'?
   66 | pair<mod_t, mod_t> solve_rec(
      |      ^~~~~
      |      mode_t
a.cc:66:13: error: 'mod_t' was not declared in this scope; did you mean 'mode_t'?
   66 | pair<mod_t, mod_t> solve_rec(
      |             ^~~~~
      |             mode_t
a.cc:66:18: error: template argument 1 is invalid
   66 | pair<mod_t, mod_t> solve_rec(
      |                  ^
a.cc:66:18: error: template argument 2 is invalid
a.cc: In function 'int solve_rec(const std::vector<int>&, int, int, int)':
a.cc:77:5: error: 'mod_t' was not declared in this scope; did you mean 'mode_t'?
   77 |     mod_t stripe_res = pow(mod_t(2), h[l] - current_h);
      |     ^~~~~
      |     mode_t
a.cc:78:10: error: expected ';' before 'nonstripe_res'
   78 |     mod_t nonstripe_res = pow(mod_t(2), r - l) - mod_t(2);    // -2 for stripe
      |          ^~~~~~~~~~~~~~
      |          ;
a.cc:79:22: error: 'stripe_res' was not declared in this scope
   79 |     return make_pair(stripe_res, nonstripe_res);
      |                      ^~~~~~~~~~
a.cc:79:34: error: 'nonstripe_res' was not declared in this scope
   79 |     return make_pair(stripe_res, nonstripe_res);
      |                                  ^~~~~~~~~~~~~
a.cc:94:3: error: 'mod_t' was not declared in this scope; did you mean 'mode_t'?
   94 |   mod_t nonstripe_res(1);
      |   ^~~~~
      |   mode_t
a.cc:95:8: error: expected ';' before 'stripe_res'
   95 |   mod_t stripe_res(1);
      |        ^~~~~~~~~~~
      |        ;
a.cc:97:15: error: template argument 2 is invalid
   97 |   vector<mod_t> stripe, nonstripe;
      |               ^
a.cc:99:10: error: expected ';' before 'stripe'
   99 |     mod_t stripe, nonstripe;
      |          ^~~~~~~
      |          ;
a.cc:100:62: error: no match for 'operator=' (operand types are 'std::tuple<int&, int&>' and 'int')
  100 |     tie(stripe, nonstripe) = solve_rec(h, ls[i], rs[i], new_h);
      |                                                              ^
In file included from /usr/include/c++/14/bits/memory_resource.h:47,
                 from /usr/include/c++/14/string:68,
                 from /usr/include/c++/14/bits/locale_classes.h:40,
                 from /usr/include/c++/14/bits/ios_base.h:41,
                 from /usr/include/c++/14/ios:44,
                 from /usr/include/c++/14/ostream:40,
                 from /usr/include/c++/14/iostream:41,
                 from a.cc:3:
/usr/include/c++/14/tuple:2355:9: note: candidate: 'template<class _U1, class _U2> std::__enable_if_t<((bool)__assignable<const _U1&, const _U2&>()), std::tuple<_T1, _T2>&> std::tuple<_T1, _T2>::operator=(const std::tuple<_U1, _U2>&) [with _U2 = _U1; _T1 = int&; _T2 = int&]'
 2355 |         operator=(const tuple<_U1, _U2>& __in)
      |         ^~~~~~~~
/usr/include/c++/14/tuple:2355:9: note:   template argument deduction/substitution failed:
a.cc:100:62: note:   mismatched types 'const std::tuple<_T1, _T2>' and 'int'
  100 |     tie(stripe, nonstripe) = solve_rec(h, ls[i], rs[i], new_h);
      |                                                              ^
/usr/include/c++/14/tuple:2365:9: note: candidate: 'template<class _U1, class _U2> std::__enable_if_t<((bool)__assignable<_U1, _U2>()), std::tuple<_T1, _T2>&> std::tuple<_T1, _T2>::operator=(std::tuple<_U1, _U2>&&) [with _U2 = _U1; _T1 = int&; _T2 = int&]'
 2365 |         operator=(tuple<_U1, _U2>&& __in)
      |         ^~~~~~~~
/usr/include/c++/14/tuple:2365:9: note:   template argument deduction/substitution failed:
a.cc:100:62: note:   mismatched types 'std::tuple<_T1, _T2>' and 'int'
  100 |     tie(stripe, nonstripe) = solve_rec(h, ls[i], rs[i], new_h);
      |                                                              ^
/usr/include/c++/14/tuple:2375:9: note: candidate: 'template<class _U1, class _U2> std::__enable_if_t<((bool)__assignable<const _U1&, const _U2&>()), std::tuple<_T1, _T2>&> std::tuple<_T1, _T2>::operator=(const std::pair<_U1, _U2>&) [with _U2 = _U1; _T1 = int&; _T2 = int&]'
 2375 |         operator=(const pair<_U1, _U2>& __in)
      |         ^~~~~~~~
/usr/include/c++/14/tuple:2375:9: note:   template argument deduction/substitution failed:
a.cc:100:62: note:   mismatched types 'const std::pair<_T1, _T2>' and 'int'
  100 |     tie(stripe, nonstripe) = solve_rec(h, ls[i], rs[i], new_h);
      |                                                              ^
/usr/include/c++/14/tuple:2386:9: note: candidate: 'template<class _U1, class _U2> std::__enable_if_t<((bool)__assignable<_U1, _U2>()), std::tuple<_T1, _T2>&> std::tuple<_T1, _T2>::operator=(std::pair<_U1, _U2>&&) [with _U2 = _U1; _T1 = int&; _T2 = int&]'
 2386 |         operator=(pair<_U1, _U2>&& __in)
      |         ^~~~~~~~
/usr/include/c++/14/tuple:2386:9: note:   template argument deduction/substitution failed:
a.cc:100:62: note:   mismatched types 'std::pair<_T1, _T2>' and 'int'
  100 |     tie(stripe, nonstripe) = solve_rec(h, ls[i], rs[i], new_h);
      |                                                              ^
/usr/include/c++/14/tuple:2332:7: note: candidate: 'std::tuple<_T1, _T2>& std::tuple<_T1, _T2>::operator=(std::__conditional_t<((bool)__assignable<const _T1&, const _T2&>()), const std::tuple<_T1, _T2>&, const std::__nonesuch&>) [with _T1 = int&; _T2 = int&; std::__conditional_t<((bool)__assignable<const _T1&, const _T2&>()), const std::tuple<_T1, _T2>&, const std::__nonesuch&> = const std::tuple<int&, int&>&]'
 2332 |       operator=(__conditional_t<__assignable<const _T1&, const _T2&>(),
      |       ^~~~~~~~
/usr/include/c++/14/tuple:2334:52: note:   no known conversion for argument 1 from 'int' to 'std::__conditional_t<true, const std::tuple<int&, int&>&, const std::__nonesuch&>' {aka 'const std::tuple<int&, int&>&'}
 2332 |       operator=(__conditional_t<__assignable<const _T1&, const _T2&>(),
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 2333 |                                 const tuple&,
      |                                 ~~~~~~~~~~~~~       
 2334 |                                 const __nonesuch&> __in)
      |                                 ~~~~~~~~~~~~~~~~~~~^~~~
/usr/include/c++/14/tuple:2343:7: note: candidate: 'std::tuple<_T1, _T2>& std::tuple<_T1, _T2>::operator=(std::__conditional_t<((bool)__assignable<_T1, _T2>()), std::tuple<_T1, _T2>&&, std::__nonesuch&&>) [with _T1 = int&; _T2 = int&; std::__conditional_t<((bool)__assignable<_T1, _T2>()), std::tuple<_T1, _T2>&&, std::__nonesuch&&> = std::tuple<int&, int&>&&]'
 2343 |       operator=(__conditional_t<__assignable<_T1, _T2>(),
      |       ^~~~~~~~
/usr/include/c++/14/tuple:2345:47: note:   no known conversion for argument 1 from 'int' to 'std::__conditional_t<true, std::tuple<int&, int&>&&, std::__nonesuch&&>' {aka 'std::tuple<int&, int&>&&'}
 2343 |       operator=(__conditional_t<__assignable<_T1, _T2>(),
      |                 ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
 2344 |                                 tuple&&,
      |                                 ~~~~~~~~       
 2345 |                                 __nonesuch&&> __in)
      |                                 ~~~~~~~~~~~~~~^~~~
a.cc:101:5: error: 'nonstripe_res' was not declared in this scope; did you mean 'nonstripe'?
  101 |     nonstripe_res *= nonstripe + (stripe * mod_t(2));
      |     ^~~~~~~~~~~~~
      |     nonstripe
a.cc:102:5: error: 'stripe_res' was not declared in this scope; did you mean 'stripe'?
  102 |     stripe_res *= stripe;
      |     ^~~~~~~~~~
      |     stripe
a.cc:104:50: error: 'nonstripe_res' was not declared in this scope; did you mean 'nonstripe'?
  104 |   for (int i = l; i < r; ++i) if (h[i] == new_h) nonstripe_res *= mod_t(2);
      |                                                  ^~~~~~~~~~~~~
      |                                                  nonstripe
a.cc:105:3: error: 'nonstripe_res' was not declared in this scope; did you mean 'nonstripe'?
  105 |   nonstripe_res -= stripe_res * mod_t(2);
      |   ^~~~~~~~~~~~~
      |   nonstripe
a.cc:105:20: error: 'stripe_res' was not declared in this scope; did you mean 'stripe'?
  105 |   nonstripe_res -= stripe_res * mod_t(2);
      |                    ^~~~~~~~~~
      |                    stripe
a.cc:106:17: error: 'pow' was not declared in this scope
  106 |   stripe_res *= pow(mod_t(2), new_h - current_h);
      |                 ^~~
a.cc: In function 'int main()':
a.cc:117:17: error: 'mod_t' was not declared in this scope; did you mean 'mode_t'?
  117 |     cout << pow(mod_t(2), h[0]).get() << endl;
      |                 ^~~~~
      |                 mode_t
a.cc:117:13: error: 'pow' was not declared in this scope
  117 |     cout << pow(mod_t(2), h[0]).get() << endl;
      |             ^~~
a.cc:120:3: error: 'mod_t' was not declared in this scope; did you mean 'mode_t'?
  120 |   mod_t precompute(1);
      |   ^~~~~
      |   mode_t
a.cc:124:7: error: 'precompute' was not declared in this scope
  124 |       precompute *= pow(mod_t(2), h[i] - adj);
      |       ^~~~~~~~~~
a.c