fork download
copy 
  1. // عَجَبًا لأَمْرِ المُؤْمِنِ، إنَّ أمْرَهُ كُلَّهُ خَيْرٌ
  2. #include <bits/stdc++.h>
  3. using namespace std;
  4. using ll = long long;
  5. using ld = double;
  6. const char el = '\n';
  7.  
  8. const int MOD = 1e9 + 7;
  9. const ll LIMIT = LLONG_MAX - 1ll * (MOD - 1) * (MOD - 1);
  10. const int M = 2, N = 2e5 + 9;
  11.  
  12. using matrix = array<array<ll, M>, M>;
  13.  
  14. matrix operator*(const matrix &a, const matrix &b) {
  15. 	matrix res{};
  16. 	for (int i = 0; i < M; ++i) {
  17. 		ll row[M] = {};
  18. 		for (int j = 0; j < M; ++j) {
  19. 			ll r = a[i][j];
  20. 			if (!r) continue;
  21. 			for (int k = 0; k < M; ++k) {
  22. 				row[k] += r * b[j][k];
  23. 				if (row[k] > LIMIT || row[k] < -LIMIT) {
  24. 					row[k] %= MOD;
  25. 				}
  26. 			}
  27. 		}
  28. 		for (int k = 0; k < M; ++k) {
  29. 			row[k] %= MOD;
  30. 			if (row[k] < 0) row[k] += MOD;
  31. 			res[i][k] = row[k];
  32. 		}
  33. 	}
  34. 	return res;
  35. }
  36.  
  37. matrix Identity(int n) {
  38. 	matrix ret = {};
  39. 	for (int i = 0; i < n; ++i)
  40. 		ret[i][i] = 1;
  41. 	return ret;
  42. }
  43.  
  44. matrix mat_power(matrix x, ll p) {
  45. 	matrix res = Identity(x.size());
  46. 	while (p) {
  47. 		if (p & 1) res = (res * x);
  48. 		x = (x * x);
  49. 		p >>= 1;
  50. 	}
  51. 	return res;
  52. }
  53.  
  54. matrix f(char c) {
  55. 	switch (c) {
  56. 		case '*': return {
  57. 				{
  58. 					{0, 0},
  59. 					{1, 0}
  60. 				}
  61. 			};
  62. 		case 'S': return {
  63. 				{
  64. 					{1, 1},
  65. 					{0, 0}
  66. 				}
  67. 			};
  68. 		case 'D': return {
  69. 				{
  70. 					{1, 1},
  71. 					{0, 0}
  72. 				}
  73. 			};
  74. 		case 'H': return {
  75. 				{
  76. 					{0, 0},
  77. 					{1, 1}
  78. 				}
  79. 			};
  80. 		case 'A': return {
  81. 				{
  82. 					{0, 1},
  83. 					{1, 0}
  84. 				}
  85. 			};
  86. 		case 'E': return {
  87. 				{
  88. 					{0, 1},
  89. 					{1, 0}
  90. 				}
  91. 			};
  92. 		case 'I': return {
  93. 				{
  94. 					{0, 1},
  95. 					{1, 0}
  96. 				}
  97. 			};
  98. 		case 'O': return {
  99. 				{
  100. 					{0, 1},
  101. 					{1, 0}
  102. 				}
  103. 			};
  104. 		case 'U': return {
  105. 				{
  106. 					{0, 1},
  107. 					{1, 0}
  108. 				}
  109. 			};
  110. 		case '?': return {
  111. 				{
  112. 					{20, 7},
  113. 					{6, 19}
  114. 				}
  115. 			};
  116. 		default: return {
  117. 				{
  118. 					{1, 0},
  119. 					{0, 1}
  120. 				}
  121. 			};
  122. 	}
  123. }
  124.  
  125. matrix tr[N << 2];
  126.  
  127. void upd(int i, int l, int r, int idx, char c) {
  128. 	if (l == r) {
  129. 		tr[i] = f(c);
  130. 		return;
  131. 	}
  132. 	int m = l + r >> 1;
  133. 	if (idx <= m) {
  134. 		upd(i << 1, l, m, idx, c);
  135. 	} else upd(i << 1 | 1, m + 1, r, idx, c);
  136. 	tr[i] = tr[i << 1] * tr[i << 1 | 1];
  137. }
  138.  
  139. void ama_aan() {
  140. 	int n, q;
  141. 	string s;
  142. 	cin >> n >> q >> s;
  143. 	upd(1, 0, n, 0, '*');
  144. 	for (int i = 0; i < n; i++)
  145. 		upd(1, 0, n, i + 1, s[i]);
  146. 	cout << tr[1][1][0] << el;
  147. 	while (q--) {
  148. 		int i;
  149. 		char c;
  150. 		cin >> i >> c;
  151. 		upd(1, 1, n, i, c);
  152. 		cout << tr[1][1][0] << el;
  153. 	}
  154. }
  155.  
  156. signed main() {
  157. 	cin.tie(0)->sync_with_stdio(0);
  158. 	cout << fixed << setprecision(10);
  159. #if Mosaab
  160. 	freopen("input.txt", "r", stdin);
  161. 	freopen("output.txt", "w", stdout);
  162. #endif
  163. 	int t = 1;
  164. 	// cin >> t;
  165. 	while (t--) ama_aan();
  166. }
  167.  
  168.  
Success #stdin #stdout 0s 5324KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
1
https://ideone.com/vjH7ba
language:
C++ (gcc 8.3)
created:
1 day 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!