fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. using vi = vector<int>;
  4. #define FOR(i, a, b) for (int i = (a); i < (b); i++)
  5. #define all(x) x.begin(), x.end()
  6. #define endl '\n'
  7.  
  8. using ll = long long;
  9.  
  10. template <int MOD>
  11. struct mint {
  12.     int v;
  13.  
  14.     mint(ll x = 0) : v(int(-MOD < x && x < MOD ? x : x % MOD) + (x < 0) * MOD) {}
  15.  
  16.     friend mint pow(mint base, ll exp) {
  17.         mint res = 1;
  18.         while (exp) {
  19.             if (exp & 1) {
  20.                 res *= base;
  21.             }
  22.             base *= base;
  23.             exp >>= 1;
  24.         }
  25.         return res;
  26.     }
  27.  
  28.     mint &operator+=(mint b) {
  29.         v = v + b.v - (v + b.v >= MOD) * MOD;
  30.         return *this;
  31.     }
  32.     mint &operator-=(mint b) {
  33.         v = v - b.v + (v < b.v) * MOD;
  34.         return *this;
  35.     }
  36.     mint &operator*=(mint b) {
  37.         v = int(1ll * v * b.v % MOD);
  38.         return *this;
  39.     }
  40.     mint &operator/=(mint b) {
  41.         v = int(1ll * v * pow(b, MOD - 2).v % MOD);
  42.         return *this;
  43.     }
  44.     friend mint operator+(mint a, mint b) {
  45.         return a += b;
  46.     }
  47.     friend mint operator-(mint a, mint b) {
  48.         return a -= b;
  49.     }
  50.     friend mint operator*(mint a, mint b) {
  51.         return a *= b;
  52.     }
  53.     friend mint operator/(mint a, mint b) {
  54.         return a /= b;
  55.     }
  56.     friend ostream &operator<<(ostream &os, mint a) {
  57.         return os << a.v;
  58.     }
  59. };
  60.  
  61. using mi = mint<998244353>;
  62.  
  63. void solve() {
  64. 	int n, m; cin >> n >> m;
  65. 	vi a(n); FOR(i, 0, n) cin >> a[i];
  66. 	vi p(n), s(n);
  67. 	int mn = m;
  68. 	FOR(i, 0, n) {
  69. 		if (a[i] != -1) mn = min(mn, a[i]);
  70. 		p[i] = mn;
  71. 	}
  72. 	int mx = 1;
  73. 	for (int i = n - 1; i >= 0; i--) {
  74. 		if (a[i] != -1) mx = max(mx, a[i]);
  75. 		s[i] = mx;
  76. 	}
  77. 	vi c(n);
  78. 	FOR(i, 0, n) {
  79. 		c[i] = a[i] == -1;
  80. 		if (i) c[i] += c[i - 1];
  81. 	}
  82. 	mi ans = 0;
  83. 	FOR(i, 0, n - 1) {
  84. 		int x = c[i], y = c[n - 1] - c[i];
  85. 		FOR(j, s[i + 1], p[i]) {
  86. 			ans += pow(m - j, x) * pow(j, y);
  87. 		}
  88. 		FOR(j, s[i + 1], p[i] - 1) {
  89. 			ans -= pow(m - j - 1, x) * pow(j, y);
  90. 		}
  91. 	}
  92. 	ans += pow(m, c[n - 1]);
  93. 	cout << ans << endl;
  94. }
  95.  
  96. signed main() {
  97.   ios::sync_with_stdio(0); cin.tie(0);
  98.   int t = 1; while (t--) solve();
  99. }
  100.  
  101.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
11 12
-1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
stdout
copy 
529513150
https://ideone.com/J8Aztv
language:
C++ (gcc 8.3)
created:
2 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!