fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. template <int MOD_> struct modnum {
  5. 	static constexpr int MOD = MOD_;
  6. 	static_assert(MOD_ > 0, "MOD must be positive");
  7.  
  8. private:
  9. 	using ll = long long;
  10.  
  11. 	int v;
  12.  
  13. 	static int minv(int a, int m) {
  14. 		a %= m;
  15. 		assert(a);
  16. 		return a == 1 ? 1 : int(m - ll(minv(m, a)) * ll(m) / a);
  17. 	}
  18.  
  19. public:
  20.  
  21. 	modnum() : v(0) {}
  22. 	modnum(ll v_) : v(int(v_ % MOD)) { if (v < 0) v += MOD; }
  23. 	explicit operator int() const { return v; }
  24. 	friend std::ostream& operator << (std::ostream& out, const modnum& n) { return out << int(n); }
  25. 	friend std::istream& operator >> (std::istream& in, modnum& n) { ll v_; in >> v_; n = modnum(v_); return in; }
  26.  
  27. 	friend bool operator == (const modnum& a, const modnum& b) { return a.v == b.v; }
  28. 	friend bool operator != (const modnum& a, const modnum& b) { return a.v != b.v; }
  29.  
  30. 	modnum inv() const {
  31. 		modnum res;
  32. 		res.v = minv(v, MOD);
  33. 		return res;
  34. 	}
  35. 	friend modnum inv(const modnum& m) { return m.inv(); }
  36. 	modnum neg() const {
  37. 		modnum res;
  38. 		res.v = v ? MOD-v : 0;
  39. 		return res;
  40. 	}
  41. 	friend modnum neg(const modnum& m) { return m.neg(); }
  42.  
  43. 	modnum operator- () const {
  44. 		return neg();
  45. 	}
  46. 	modnum operator+ () const {
  47. 		return modnum(*this);
  48. 	}
  49.  
  50. 	modnum& operator ++ () {
  51. 		v ++;
  52. 		if (v == MOD) v = 0;
  53. 		return *this;
  54. 	}
  55. 	modnum& operator -- () {
  56. 		if (v == 0) v = MOD;
  57. 		v --;
  58. 		return *this;
  59. 	}
  60. 	modnum& operator += (const modnum& o) {
  61. 		v += o.v;
  62. 		if (v >= MOD) v -= MOD;
  63. 		return *this;
  64. 	}
  65. 	modnum& operator -= (const modnum& o) {
  66. 		v -= o.v;
  67. 		if (v < 0) v += MOD;
  68. 		return *this;
  69. 	}
  70. 	modnum& operator *= (const modnum& o) {
  71. 		v = int(ll(v) * ll(o.v) % MOD);
  72. 		return *this;
  73. 	}
  74. 	modnum& operator /= (const modnum& o) {
  75. 		return *this *= o.inv();
  76. 	}
  77.  
  78. 	friend modnum operator ++ (modnum& a, int) { modnum r = a; ++a; return r; }
  79. 	friend modnum operator -- (modnum& a, int) { modnum r = a; --a; return r; }
  80. 	friend modnum operator + (const modnum& a, const modnum& b) { return modnum(a) += b; }
  81. 	friend modnum operator - (const modnum& a, const modnum& b) { return modnum(a) -= b; }
  82. 	friend modnum operator * (const modnum& a, const modnum& b) { return modnum(a) *= b; }
  83. 	friend modnum operator / (const modnum& a, const modnum& b) { return modnum(a) /= b; }
  84. };
  85.  
  86. template <typename T> T pow(T a, long long b) {
  87. 	assert(b >= 0);
  88. 	T r = 1; while (b) { if (b & 1) r *= a; b >>= 1; a *= a; } return r;
  89. }
  90.  
  91. using num = modnum<int(1e9)+7>;
  92.  
  93. template <typename K, typename V>
  94. using hash_map = unordered_map<K, V>;
  95.  
  96. const int MAXN = 1.1e5;
  97. const int M = 1e9;
  98. int N, K;
  99. int A[MAXN];
  100. int B[MAXN];
  101.  
  102. num go(int v, const vector<int>& inds, const vector<int>& intervals) {
  103. 	int L = int(intervals.size());
  104. 	vector<num> res(L+1); res[0] = 1;
  105. 	num totVal = res[0];
  106.  
  107. 	num mult = 1;
  108. 	num imult = 1;
  109. 	num r = M-v;
  110. 	num inv = (r == 0 ? num(1) : r.inv());
  111.  
  112. 	int lo = 0, hi = 1;
  113. 	for (int i : inds) {
  114. 		while (hi <= L && intervals[hi-1] <= i) {
  115. 			hi++;
  116. 		}
  117. 		while (intervals[lo]+K <= i) {
  118. 			totVal -= res[lo] * mult;
  119. 			lo++;
  120. 		}
  121.  
  122. 		num curVal = totVal;
  123. 		mult *= r;
  124. 		imult *= inv;
  125. 		totVal *= r;
  126. 		totVal += curVal;
  127. 		res[hi-1] += curVal * imult;
  128. 	}
  129.  
  130. 	return res.back() * mult;
  131. }
  132.  
  133. int main() {
  134. 	ios::sync_with_stdio(0), cin.tie(0);
  135.  
  136. 	cin >> N >> K;
  137. 	for (int i = 0; i < N-K+1; i++) {
  138. 		cin >> A[i];
  139. 	}
  140.  
  141. 	// set max
  142. 	{
  143. 		deque<pair<int, int>> dq;
  144. 		for (int i = 0; i < N; i++) {
  145. 			if (i < N-K+1) {
  146. 				pair<int, int> val(A[i], i);
  147. 				while (!dq.empty() && dq.back() < val) {
  148. 					dq.pop_back();
  149. 				}
  150. 				dq.push_back(val);
  151. 			}
  152. 			if (dq.front().second == i-K) {
  153. 				dq.pop_front();
  154. 			}
  155. 			assert(!dq.empty());
  156. 			B[i] = dq.front().first;
  157. 		}
  158.  
  159. 		//for (int i = 0; i < N; i++) { cerr << B[i] << " \n"[i+1==N]; }
  160. 	}
  161.  
  162. 	hash_map<int, vector<int>> inds;
  163. 	hash_map<int, vector<int>> intervals; // lefts
  164. 	for (int i = 0; i < N; i++) {
  165. 		inds[B[i]].push_back(i);
  166. 	}
  167. 	for (int i = 0; i < N-K+1; i++) {
  168. 		intervals[A[i]].push_back(i);
  169. 	}
  170.  
  171. 	num ans = 1;
  172. 	for (auto it : intervals) {
  173. 		int v = it.first;
  174. 		ans *= go(v, inds[v], it.second);
  175. 	}
  176. 	cout << ans << '\n';
  177.  
  178. 	return 0;
  179. }
  180.  
Success #stdin #stdout 0s 4476KB
comments (?)
stdin
copy 
4 2
999999998
999999999
999999998
stdout
copy 
3
https://ideone.com/5Nu2j2
language:
C++14 (gcc 8.3)
created:
4 years 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!