Guest User

Untitled

a guest
Sep 12th, 2021
74
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <iostream>
  2. #include <algorithm>
  3. #include <vector>
  4. #include <set>
  5. #include <map>
  6. #include <string>
  7. using namespace std;
  8.  
  9. const long long MOD = 1e9 + 7;
  10.  
  11. long long gNaive(const string &s) {
  12.     vector<pair<int, int>> pos;
  13.     for (int i = 0; i < s.size(); i++) {
  14.         if (s[i] == 'X')
  15.             pos.push_back({ 1, i });
  16.         if (s[i] == 'O')
  17.             pos.push_back({ 2, i });
  18.     }
  19.  
  20.     long long res = 0;
  21.  
  22.     for (int i = 1; i < pos.size(); i++) {
  23.         if (pos[i - 1].first == pos[i].first)
  24.             continue;
  25.  
  26.         long long l = pos[i - 1].second + 1;
  27.         long long r = s.size() - pos[i].second;
  28.  
  29.         res = (res + l * r % MOD) % MOD;
  30.     }
  31.  
  32.     return res;
  33. }
  34.  
  35. long long g(const string &s) {
  36.     long long len = 0;
  37.     long long sumL = 0;
  38.     long long sumR = 0;
  39.     long long sumLR = 0;
  40.  
  41.     long long firstO = -1;
  42.     long long firstX = -1;
  43.     long long lastO = -1;
  44.     long long lastX = -1;
  45.     long long pairCount = 0;
  46.  
  47.     char firstChar = '?';
  48.     char lastChar = '?';
  49.  
  50.     for (int i = 0; i < s.size(); i++) {
  51.         if (s[i] == 'F') {
  52.  
  53.             len = (len + 1) % MOD;
  54.             sumR = (sumR + pairCount) % MOD;
  55.             sumLR = (sumLR + sumL) % MOD;
  56.  
  57.         } else if (s[i] == 'O') {
  58.  
  59.             len = (len + 1) % MOD;
  60.             sumR = (sumR + pairCount) % MOD;
  61.             sumLR = (sumLR + sumL) % MOD;
  62.  
  63.             if (lastChar == 'X') {
  64.                 long long l = (lastX + 1) % MOD;
  65.                 long long r = 1 % MOD;
  66.  
  67.                 sumLR = (sumLR + l * r % MOD) % MOD;
  68.                 sumL = (sumL + l) % MOD;
  69.                 sumR = (sumR + r) % MOD;
  70.                 pairCount = (pairCount + 1) % MOD;
  71.             }
  72.  
  73.             if (firstChar == '?') {
  74.                 firstO = (len - 1 + MOD) % MOD;
  75.                 firstChar = 'O';
  76.             }
  77.  
  78.             lastO = (len - 1 + MOD) % MOD;
  79.             lastChar = 'O';
  80.  
  81.         } else if (s[i] == 'X') {
  82.  
  83.             len = (len + 1) % MOD;
  84.             sumR = (sumR + pairCount) % MOD;
  85.             sumLR = (sumLR + sumL) % MOD;
  86.  
  87.             if (lastChar == 'O') {
  88.                 long long l = (lastO + 1) % MOD;
  89.                 long long r = 1 % MOD;
  90.  
  91.                 sumLR = (sumLR + l * r % MOD) % MOD;
  92.                 sumL = (sumL + l) % MOD;
  93.                 sumR = (sumR + r) % MOD;
  94.                 pairCount = (pairCount + 1) % MOD;
  95.             }
  96.  
  97.             if (firstChar == '?') {
  98.                 firstX = (len - 1 + MOD) % MOD;
  99.                 firstChar = 'X';
  100.             }
  101.  
  102.             lastX = (len - 1 + MOD) % MOD;
  103.             lastChar = 'X';
  104.  
  105.         } else {
  106.  
  107.             sumLR = (sumLR * 2) % MOD;
  108.             sumLR = (sumLR + len * sumL % MOD) % MOD;
  109.             sumLR = (sumLR + len * sumR % MOD) % MOD;
  110.  
  111.             sumL = (sumL * 2) % MOD;
  112.             sumL = (sumL + pairCount * len % MOD) % MOD;
  113.  
  114.             sumR = (sumR * 2) % MOD;
  115.             sumR = (sumR + pairCount * len % MOD) % MOD;
  116.  
  117.             pairCount = (pairCount * 2) % MOD;
  118.  
  119.             if (firstChar == 'X' && lastChar == 'O') {
  120.                 long long l = (lastO + 1) % MOD;
  121.                 long long r = (len - firstX) % MOD;
  122.  
  123.                 sumLR = (sumLR + l * r % MOD) % MOD;
  124.                 sumL = (sumL + l) % MOD;
  125.                 sumR = (sumR + r) % MOD;
  126.                 pairCount = (pairCount + 1) % MOD;
  127.             }
  128.             if (firstChar == 'O' && lastChar == 'X') {
  129.                 long long l = (lastX + 1) % MOD;
  130.                 long long r = (len - firstO) % MOD;
  131.  
  132.                 sumLR = (sumLR + l * r % MOD) % MOD;
  133.                 sumL = (sumL + l) % MOD;
  134.                 sumR = (sumR + r) % MOD;
  135.                 pairCount = (pairCount + 1) % MOD;
  136.             }
  137.  
  138.             if (lastO != -1)
  139.                 lastO = (lastO + len) % MOD;
  140.             if (lastX != -1)
  141.                 lastX = (lastX + len) % MOD;
  142.             len = (len * 2) % MOD;
  143.  
  144.         }
  145.     }
  146.  
  147.     return sumLR;
  148. }
  149.  
  150. string generateString(int size, int n) {
  151.     string letters = ".FOX";
  152.     string res;
  153.     for (int i = 0; i < size; i++) {
  154.         res += letters[n % 4];
  155.         n /= 4;
  156.     }
  157.     return res;
  158. }
  159.  
  160. string expandString(string &s) {
  161.     string res;
  162.     for (char c : s) {
  163.         if (c == '.')
  164.             res += res;
  165.         else
  166.             res += c;
  167.     }
  168.     return res;
  169. }
  170.  
  171. void testG() {
  172.     for (int size = 0, limit = 4; size <= 8; size++, limit *= 4) {
  173.         for (int n = 1; n < limit; n++) {
  174.             string s = generateString(size, n);
  175.             if (s[0] == '.')
  176.                 continue;
  177.             string es = expandString(s);
  178.  
  179.             long long res = g(s);
  180.             long long resNaive = gNaive(es);
  181.  
  182.             if (res != resNaive) {
  183.                 cout << s << "\n";
  184.                 cout << es << "\n";
  185.                 cout << res << "\n";
  186.                 cout << resNaive << "\n";
  187.                 return;
  188.             }
  189.         }
  190.     }
  191.  
  192.     cerr << "Max test:";
  193.     for (int i = 0; i < 10; i++) {
  194.         string s = generateString(4e6, rand() * rand());
  195.         long long res = g(s);
  196.         cerr << res << "\n";
  197.     }
  198. }
  199.  
  200. void solve(int test) {
  201.     int n;
  202.     string s;
  203.     cin >> n >> s;
  204.  
  205.     cout << "Case #" << test << ": " << g(s) << "\n";
  206. }
  207.  
  208. int main() {
  209.     freopen("input.txt", "r", stdin);
  210.     freopen("output.txt", "w", stdout);
  211.  
  212.     //testG();
  213.  
  214.     ios_base::sync_with_stdio(0);
  215.     cin.tie(0);
  216.  
  217.     int n;
  218.     cin >> n;
  219.  
  220.     for (int test = 1; test <= n; test++)
  221.         solve(test);
  222. }
RAW Paste Data