1. #include <bits/stdc++.h>
  2. using namespace std;
  3. typedef long long ll;
  4. #define endl "\n"
  5. #define quick ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
  6. #define ALL(x) x.begin(),x.end()
  7. #define SORT(x) sort(ALL(x))
  8. #define FOR(a,b,c) for(ll (a)= (b);(a)<(c);++(a))
  9. #define REP(a,b) FOR(a,0,b)
  10. #define mp make_pair
  11. #define pb push_back
  12. #define pll pair<ll,ll>
  13. #define pii pair<int,int>
  14. #define vl vector<ll>
  15. #define vi vector<int>
  16. #define f first
  17. #define s second
  18. ll ttt = 1, case_ = 0, n;
  19. ll const MOD = 1e9+7, MAXN = 8e5+5;
  20. vector<ll> facs(MAXN), inv_facs(MAXN);
  21. ll add_(ll a, ll b) {
  22. return (a + b) % MOD;
  23. }
  24. ll sub_(ll a, ll b) {
  25. return (a + MOD - b) % MOD;
  26. }
  27. ll mult_(ll a, ll b) {
  28. return (a*b) % MOD;
  29. }
  30. ll power(ll x,ll y,ll p)
  31. {
  32. ll res = 1;
  33. x = x % p;
  34. if (x == 0) return 0;
  35. while (y > 0)
  36. {
  37. if (y & 1)
  38. res = (res*x) % p;
  39. y = y>>1; // y = y/2
  40. x = (x*x) % p;
  41. }
  42. return res;
  43. }
  44. ll div_(ll a, ll b) {
  45. return mult_(a,power(b,MOD-2,MOD));
  46. }
  47. ll ncr(ll n, ll r){
  48. if (r > n || n < 0 || r < 0) return 0;
  49. return mult_(mult_(facs[n],inv_facs[r]),inv_facs[n-r]);
  50. }
  51. void get_facs() {
  52. facs[0] = 1;
  53. for (int i = 1; i < MAXN; i++) {
  54. facs[i] = mult_(facs[i-1],i);
  55. }
  56. inv_facs[MAXN-1] = power(facs[MAXN-1],MOD-2,MOD);
  57. for (int i = MAXN-2; i >= 0; i--) {
  58. inv_facs[i] = mult_(inv_facs[i+1],i+1);
  59. }
  60. }
  61. template <class myType>
  62. void print_arr(myType &arr, ll L, string sep){ REP(i,L) {
  63. cout << arr[i]; if (i < L-1) cout << sep;
  64. } cout << endl; return; }
  65. /*
  66. When we add an F, dp[i] = dp[i-1]
  67. When we add an O, dp[i] = dp[i-1] + index of previous X
  68. When we add an X, dp[i] = dp[i-1] + index of previous O
  69. What happens when we duplicate?
  70. XOOFXO|XOOFXO - we need to immediately compute the answer for each new index. How do we do that?
  71. Treat dp[prev] = 0 as a special case: just doubles to 0
  72. dp[7] = dp[6] + 6
  73. dp[8] = dp[6] + 6 + 7
  74. dp[9] = dp[6] + 6 + 7
  75. dp[10] = dp[6] + 6 + 7
  76. dp[11] = dp[6] + 6 + 7 + 9
  77. dp[12] = dp[6] + 6 + 7 + 9 + 11
  78. The total is LEN * prev + sum( F(j) ) where j is an index which is the last of its kind in the substring
  79. Suppose that O is the last O in a block of Os and Fs, and O is at index i.
  80. F(j) = j*(pos of next different index)
  81. We can't keep track of all these indices, it's not feasible.
  82. Instead need to find a way to calculate G(S + S) based on G(S).
  83. There are 3 types of substring:
  84. 1. Entirely within first half. Total G(S)
  85. 2. Entirely within second half. Total G(S)
  86. 3. Starts in first half, ends in second half.
  87. XOOFXO|XOOFXO
  88. Every one that starts in the first half and ends in the second half has a change in the middle if first_non_f != last_non_f
  89. How many times does each change get counted? A change has two key values [prev_idx, new_idx], and the number of substrings which incorporate that change is
  90. prev_idx * (LEN - new_idx + 1)
  91. When we duplicate, each change in the first half is counted by prev_idx*LEN additional times
  92. Each change in the second half is counted by LEN*(LEN - new_idx + 1) times
  93. And there may be a new change introduced which would be counted last_idx * (LEN - first_idx + 1) times
  94. And our new set of indices is equal to our old set plus LEN, so we have (i0, i2, ..., ix, i0 + LEN, ..., ix + LEN)
  95. Suppose we have a set of changes marked [l_dist, r_dist]
  96. The new set of changes is [l_dist, r_dist + LEN], [l_dist + LEN, r_dist], and a possible extra one in the middle
  97. sum ( l_dist*(r_dist + LEN) + (l_dist + LEN)*r_dist ) (plus the extra one maybe)
  98. = 2*l_dist*r_dist + LEN*(sum(l_dist) + sum(r_dist)) = 2*G(S) + LEN*sum(l_dist + r_dist) + one in the middle
  99. How does everything morph in transition?
  100. sum(l_dist) -> l_dist + num_changes*LEN + l_dist + possible extra
  101. sum(r_dist) -> r_dist + num_changes*LEN + r_dist + possible extra
  102. The 'possible extra' l_dist is equal to the index of the last non-F and the r_dist is equal to the first non-F + LEN
  103. If we add an F on the end, what happens? Each r_dist value increases by 1
  104. [l_dist, r_dist + 1] = l_dist*r_dist + l_
  105. L1*(R1 + 1), L2*(R1 + 2), etc
  106. If we add an O on the end, all the same things are true but we might be creating a new change as well
  107. */
  108. void solve() {
  109. case_++;
  110. cout << "Case #" << case_ << ": ";
  111. cin >> n;
  112. string S;
  113. cin >> S;
  114. ll curr = -1, prev_x = -1, first_x = -1, prev_o = -1, first_o = -1, LEN = 0, ans = 0, l_dist = 0, r_dist = 0, num_changes = 0;
  115. for(char c: S) {
  116. if (c == 'F') {
  117. LEN = add_(LEN, 1);
  118. ans = add_(ans, l_dist);
  119. r_dist = add_(r_dist,num_changes);
  120. }
  121. else if (c == 'O') {
  122. LEN = add_(LEN, 1);
  123. if (first_o == -1 && first_x == -1) first_o = LEN;
  124. prev_o = LEN;
  125. ans = add_(ans, l_dist);
  126. if (curr == 1) {
  127. l_dist = add_(l_dist, prev_x);
  128. num_changes = add_(num_changes,1);
  129. ans = add_(ans, prev_x);
  130. }
  131. r_dist = add_(r_dist, num_changes);
  132. curr = 0;
  133. }
  134. else if (c == 'X') {
  135. LEN = add_(LEN, 1);
  136. if (first_x == -1 && first_o == -1) first_x = LEN;
  137. prev_x = LEN;
  138. ans = add_(ans, l_dist);
  139. if (curr == 0) {
  140. l_dist = add_(l_dist, prev_o);
  141. num_changes = add_(num_changes,1);
  142. ans = add_(ans, prev_o);
  143. }
  144. r_dist = add_(r_dist, num_changes);
  145. curr = 1;
  146. }
  147. else {
  148. ll tmp = mult_(ans,2);
  149. tmp = add_(tmp, mult_(LEN,add_(l_dist,r_dist)));
  150. l_dist = add_(mult_(l_dist,2), mult_(num_changes,LEN));
  151. r_dist = add_(mult_(r_dist,2), mult_(num_changes,LEN));
  152. num_changes = mult_(num_changes,2);
  153. //cout << tmp << endl;
  154. if (first_x == -1 && first_o >= 0 && prev_x > prev_o) {
  155. // add a change
  156. num_changes = add_(num_changes,1);
  157. tmp = add_(tmp,mult_(prev_x, sub_(add_(LEN,1), first_o)));
  158. l_dist = add_(l_dist, prev_x);
  159. r_dist = add_(r_dist, sub_(add_(LEN,1), first_o));
  160. }
  161. else if (first_o == -1 && first_x >= 0 && prev_o > prev_x) {
  162. num_changes = add_(num_changes,1);
  163. tmp = add_(tmp,mult_(prev_o, sub_(add_(LEN,1), first_x)));
  164. //cout << prev_o << " " << LEN+1-first_x << endl;
  165. l_dist = add_(l_dist, prev_o);
  166. r_dist = add_(r_dist, sub_(add_(LEN,1), first_x));
  167. }
  168. prev_x = add_(prev_x, LEN);
  169. prev_o = add_(prev_o, LEN);
  170. LEN = mult_(LEN,2);
  171. ans = tmp;
  172. }
  173. //cout << LEN << ": " << l_dist << " " << r_dist << " " << ans << endl;
  174. //cout << LEN << ": " << ans << endl;
  175. }
  176. cout << ans << endl;
  177. return;
  178. }
  179. int main(){
  180. quick;
  181. freopen("C_in.txt", "r", stdin);
  182. freopen("C_out.txt", "w", stdout);
  183. cin >> ttt;
  184. while (ttt--) solve();
  185. return 0;
  186. }
Comments powered by Disqus