fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define endl '\n'
  3.  
  4. //#pragma GCC optimize ("O3")
  5. //#pragma GCC target ("sse4")
  6.  
  7. #define SZ(x) ((int)x.size())
  8. #define ALL(V) V.begin(), V.end()
  9. #define L_B lower_bound
  10. #define U_B upper_bound
  11. #define pb push_back
  12.  
  13. using namespace std;
  14. template<class T, class T2> inline int chkmax(T &x, const T2 &y) { return x < y ? x = y, 1 : 0; }
  15. template<class T, class T2> inline int chkmin(T &x, const T2 &y) { return x > y ? x = y, 1 : 0; }
  16. const int MAXN = (1 << 20);
  17. const int mod = (int)1e9 + 7;
  18. const int bound = (int)1e9 + 1;
  19.  
  20. template<class T>
  21. T pw(T a, int pw)
  22. {
  23. 	T ret(1);
  24. 	while(pw)
  25. 	{
  26. 		if(pw & 1) ret *= a; 
  27. 		a *= a;
  28. 		pw >>= 1;
  29. 	}
  30.  
  31. 	return ret;
  32. }
  33.  
  34. template<unsigned mod>
  35. class Modint 
  36. {
  37. 	private:
  38. 		unsigned x;
  39.  
  40. 	public:
  41. 		Modint() { x = 0; }
  42. 		Modint(unsigned _x) { x = _x; }
  43. 		operator unsigned() { return x; }
  44.  
  45. 		Modint operator==(const Modint& m) const { return x == m.x; }
  46. 		Modint operator!=(const Modint& m) const { return x != m.x; }
  47.  
  48. 		Modint operator+=(const Modint& m) { x = (x + m.x >= mod ? x + m.x - mod : x + m.x); return *this; }
  49. 		Modint operator-=(const Modint& m) { x = (x < m.x ? x - m.x + mod : x - m.x); return *this; }
  50. 		Modint operator*=(const Modint& m) { x = 1ULL * x * m.x % mod; return *this; }
  51.  
  52. 		Modint operator+=(const int32_t m) { x = (x + (m % mod) >= mod ? x + (m % mod) - mod : x + (m % mod)); return *this; }
  53. 		Modint operator-=(const int32_t m) { x = (x < (m % mod) ? x - (m % mod) + mod : x - (m % mod)); return *this; }
  54. 		Modint operator*=(const int32_t m) { x = 1ULL * x * (m % mod) % mod; return *this; }
  55.  
  56. 		Modint operator+=(const int64_t m) { x = (x + (m % mod) >= mod ? x + (m % mod) - mod : x + (m % mod)); return *this; }
  57. 		Modint operator-=(const int64_t m) { x = (x < (m % mod) ? x - (m % mod) + mod : x - (m % mod)); return *this; }
  58. 		Modint operator*=(const int64_t m) { x = 1ULL * x * (m % mod) % mod; return *this; }
  59.  
  60. 		Modint operator+(const Modint& m) const { return Modint(*this) += m; }
  61. 		Modint operator-(const Modint& m) const { return Modint(*this) -= m; }
  62. 		Modint operator*(const Modint& m) const { return Modint(*this) *= m; }
  63.  
  64. 		Modint operator+(const int32_t m) const { return Modint(*this) += m; }
  65. 		Modint operator-(const int32_t m) const { return Modint(*this) -= m; }
  66. 		Modint operator*(const int32_t m) const { return Modint(*this) *= m; }
  67.  
  68. 		Modint operator+(const int64_t m) const { return Modint(*this) += m; }
  69. 		Modint operator-(const int64_t m) const { return Modint(*this) -= m; }
  70. 		Modint operator*(const int64_t m) const { return Modint(*this) *= m; }
  71.  
  72. 		Modint inv() { return pw(Modint(*this), mod - 2); }		
  73. };
  74.  
  75. Modint<mod> fact[MAXN], ifact[MAXN];
  76.  
  77. void precompute()
  78. {
  79. 	fact[0] = 1;
  80. 	for(int i = 1; i < MAXN; i++) fact[i] = fact[i - 1] * i;
  81. 	ifact[MAXN - 1] = fact[MAXN - 1].inv();
  82. 	for(int i = MAXN - 2; i >= 0; i--) ifact[i] = ifact[i + 1] * (i + 1);
  83. }
  84.  
  85. Modint<mod> C(int n, int k) 
  86. {  
  87. 	if(n < k || n < 0 || k < 0) return Modint<mod>(0);
  88. 	return fact[n] * ifact[n - k] * ifact[k];
  89. } 
  90.  
  91. int n, k;
  92. int a[MAXN];
  93.  
  94. pair<int, int> tr[4 * MAXN];
  95.  
  96. void init(int l, int r, int idx)
  97. {
  98. 	if(l == r)
  99. 	{
  100. 		tr[idx] = {a[l], l};
  101. 		return;
  102. 	}
  103.  
  104. 	int mid = (l + r) >> 1;
  105. 	init(l, mid, 2 * idx + 1);
  106. 	init(mid + 1, r, 2 * idx + 2);
  107.  
  108. 	tr[idx] = min(tr[2 * idx + 1], tr[2 * idx + 2]);
  109. }
  110.  
  111. pair<int, int> query(int ql, int qr, int l, int r, int idx)
  112. {
  113. 	if(ql > r || l > qr) return {(int)1e9 + 42, -1};
  114. 	if(ql <= l && r <= qr) return tr[idx];
  115.  
  116. 	int mid = (l + r) >> 1;
  117. 	return min(query(ql, qr, l, mid, 2 * idx + 1), query(ql, qr, mid + 1, r, 2 * idx + 2));
  118. }
  119.  
  120. void read()
  121. {
  122. 	cin >> n >> k;
  123. 	for(int i = 1; i <= n - k + 1; i++)
  124. 		cin >> a[i];
  125. }
  126.  
  127. Modint<mod> dp[MAXN];
  128.  
  129. Modint<mod> solve(int l, int r, int statusL, int statusR, int cnt)
  130. {
  131. 	int len = r - l + 1;
  132. 	for(int i = 0; i <= len; i++) dp[i] = 0;
  133.  
  134. 	dp[statusL] = 1;
  135. 	Modint<mod> sum = dp[statusL];
  136. 	Modint<mod> B = cnt - 1;
  137.  
  138. 	Modint<mod> P = pw(B, k);
  139. 	for(int i = statusL + 1; i <= len; i++)
  140. 	{
  141. 		dp[i] = sum;
  142. 		sum = sum * B + dp[i];
  143. 		if(i >= k) sum -= P * dp[i - k];
  144. 	}
  145.  
  146. 	if(statusR) return dp[len];
  147. 	return sum;
  148. }
  149.  
  150. Modint<mod> rec(int l, int r)
  151. {
  152. 	int L = query(l, r, 1, n - k + 1, 0).second, R = L;
  153. 	while(L != l && a[L] == a[L - 1]) L--;
  154. 	while(R != r && a[R] == a[R + 1]) R++;
  155.  
  156. 	Modint<mod> ret = 1;
  157. 	if(L != l) ret *= rec(l, L - 1);
  158. 	if(R != r) ret *= rec(R + 1, r);
  159.  
  160. 	if(L != l && R != r) ret *= solve(L + k - 1, R, 1, 1, bound - a[L]);
  161. 	else if(L != l) ret *= solve(L + k - 1, R + k - 1, 1, 0, bound - a[L]);
  162. 	else if(R != r) ret *= solve(L, R, 0, 1, bound - a[L]);
  163. 	else ret *= solve(L, R + k - 1, 0, 0, bound - a[L]);
  164.  
  165. 	return ret;
  166. }
  167.  
  168. void solve()
  169. {
  170. 	init(1, n - k + 1, 0);
  171. 	cout << rec(1, n - k + 1) << endl;
  172. }
  173.  
  174. int main()
  175. {
  176. 	freopen("tracking2.in", "r", stdin);
  177. 	freopen("tracking2.out", "w", stdout);
  178. 	ios_base::sync_with_stdio(false);
  179. 	cin.tie(NULL);
  180.  
  181. 	precompute();
  182. 	read();
  183. 	solve();
  184. 	return 0;
  185. }
  186.  
  187.  
Runtime error #stdin #stdout #stderr 0s 64392KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
stderr
copy 
terminate called after throwing an instance of 'std::ios_base::failure[abi:cxx11]'
  what():  basic_filebuf::underflow error reading the file: iostream error
https://ideone.com/8aE2bU
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

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!