fork download
  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
stdin
5 3
ABAAA
2 1 5 1 1
1 3 5
2 2 5 0 1000000000
stdout
11 3
0 1000000000