fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4.  
  5. const long long mod = 1000000007;
  6. #define ll long long
  7. struct pii
  8. {
  9. 	ll a, b;
  10. 	pii() {};
  11. 	pii(ll A, ll B) {a = A, b = B;}
  12. 	const pii operator * (const int &c) const {return pii((a * c) % mod, (b * c) % mod);}
  13. 	const pii operator + (const pii &c) const {return pii((a + c.a) % mod, (b + c.b) % mod);}
  14. };
  15. struct node
  16. {
  17. 	pii a, b;
  18. 	node() {a = pii(1, 0), b = pii(0, 1);}
  19. 	node(pii A, pii B) {a = A, b = B;}
  20. 	const node operator + (const node &c) const {return node((c.a * a.a) + (c.b * a.b), (c.a * b.a) + (c.b * b.b));}
  21. 	pii val(pii t)
  22. 	{
  23. 		return pii(((a.a * t.a) % mod + (a.b * t.b) % mod) % mod, ((b.a * t.a) % mod + (b.b * t.b) % mod) % mod);
  24. 	}
  25. 	void swap()
  26. 	{
  27. 		pii tem = a;
  28. 		a = b;
  29. 		b = tem;
  30. 	}
  31. } va[350];
  32. bool vis[350];
  33. int n, q;
  34. string s;
  35. int len;
  36.  
  37.  
  38. int main(int argc, char const *argv[])
  39. {
  40. 	cin >> n >> q >> s;
  41. 	len = (int) sqrt (n + .0) + 1;
  42.  
  43.  
  44. 	for (int i = 0; i < n; i++)
  45. 	{
  46. 		if (s[i] == 'A')
  47. 		{
  48. 			va[i / len] = (node(pii(1, 1), pii(0, 1)) + va[i / len]);
  49. 		}
  50. 		else
  51. 		{
  52. 			va[i / len] = (node(pii(1, 0), pii(1, 1)) + va[i / len]);
  53. 		}
  54. 	}
  55.  
  56. 	ll l, r, t, aa, bb;
  57. 	while (q--)
  58. 	{
  59. 		cin >> t;
  60. 		if (t == 2)
  61. 		{
  62. 			cin >> l >> r >> aa >> bb;
  63. 			l--; r--;
  64. 			node sum(pii(1, 0), pii(0, 1));
  65. 			for (int i = l; i <= r; )
  66. 				if (i % len == 0 && i + len - 1 <= r) {
  67. 					sum = va[i / len] + sum;
  68. 					i += len;
  69. 				}
  70. 				else {
  71. 					if (vis[i / len] == 0)
  72. 					{
  73. 						if (s[i] == 'A')
  74. 							sum = node(pii(1, 1), pii(0, 1)) + sum;
  75. 						else sum = node(pii(1, 0), pii(1, 1)) + sum;
  76. 					}
  77. 					else
  78. 					{
  79. 						if (s[i] == 'B')
  80. 							sum = node(pii(1, 1), pii(0, 1)) + sum;
  81. 						else sum = node(pii(1, 0), pii(1, 1)) + sum;
  82. 					}
  83. 					++i;
  84. 				}
  85. 			cout << sum.val(pii(aa, bb)).a << ' ' << sum.val(pii(aa, bb)).b << endl;
  86. 		}
  87. 		else
  88. 		{
  89. 			cin >> l >> r;
  90. 			l--; r--;
  91. 			int st = -1, en = -1;
  92. 			for (int i = l; i <= r; )
  93. 				if (i % len == 0 && i + len - 1 <= r) {
  94. 					va[i / len].swap();
  95. 					vis[i / len] = !vis[i / len];
  96. 					i += len;
  97. 				}
  98. 				else {
  99. 					if (st == -1)st = i / len;
  100. 					en = i / len;
  101. 					if (s[i] == 'A')
  102. 						s[i] = 'B';
  103. 					else s[i] = 'A';
  104. 					++i;
  105. 				}
  106. 			if (st != -1)
  107. 			{
  108. 				va[st / len] = node(pii(1, 0), pii(0, 1));
  109. 				for (int i = st; i < st + len && i < n; i++)
  110. 				{
  111. 					if (s[i] == 'A')
  112. 					{
  113. 						va[i / len] = (node(pii(1, 1), pii(0, 1)) + va[i / len]);
  114. 					}
  115. 					else
  116. 					{
  117. 						va[i / len] = (node(pii(1, 0), pii(1, 1)) + va[i / len]);
  118. 					}
  119. 				}
  120. 				if (vis[st / len])va[st / len].swap();
  121. 			}
  122. 			if (en != -1)
  123. 			{
  124. 				va[en / len] = node(pii(1, 0), pii(0, 1));
  125. 				for (int i = en; i < en + len && i < n; i++)
  126. 				{
  127. 					if (s[i] == 'A')
  128. 					{
  129. 						va[i / len] = (node(pii(1, 1), pii(0, 1)) + va[i / len]);
  130. 					}
  131. 					else
  132. 					{
  133. 						va[i / len] = (node(pii(1, 0), pii(1, 1)) + va[i / len]);
  134. 					}
  135. 				}
  136. 				if (vis[en / len])va[en / len].swap();
  137. 			}
  138. 		}
  139. 	}
  140. 	return 0;
  141. }
Success #stdin #stdout 0s 4392KB
comments (?)
stdin
copy 
5 3
ABAAA
2 1 5 1 1
1 3 5
2 2 5 0 1000000000
stdout
copy 
11 3
0 1000000000
https://ideone.com/zv11og
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!