Guest User

Untitled

a guest
Sep 12th, 2021
81
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 f(const string &s) {
  12.     vector<long long> l(s.size()), r(s.size());
  13.     l[0] = s[0] == 'O';
  14.     r[0] = s[0] == 'X';
  15.  
  16.     for (int i = 1; i < s.size(); i++) {
  17.         if (s[i] == 'X') {
  18.             l[i] = min(l[i - 1], r[i - 1] + 1);
  19.             r[i] = min(l[i - 1] + 1, r[i - 1] + 2);
  20.         } else if (s[i] == 'F') {
  21.             l[i] = min(l[i - 1], r[i - 1] + 1);
  22.             r[i] = min(l[i - 1] + 1, r[i - 1]);
  23.         } else {
  24.             l[i] = min(l[i - 1] + 2, r[i - 1] + 1);
  25.             r[i] = min(l[i - 1] + 1, r[i - 1]);
  26.         }
  27.     }
  28.  
  29.     auto res = min(l.back(), r.back());
  30.  
  31.     return res;
  32. }
  33.  
  34. long long gNaive(const string &s) {
  35.     long long res = 0;
  36.     for (int l = 0; l < s.size(); l++)
  37.         for (int r = l; r < s.size(); r++)
  38.             res = (res + f(s.substr(l, r - l + 1))) % MOD;
  39.     return res;
  40. }
  41.  
  42. long long g(const string &s) {
  43.     vector<pair<int, int>> pos;
  44.     for (int i = 0; i < s.size(); i++) {
  45.         if (s[i] == 'X')
  46.             pos.push_back({ 1, i });
  47.         if (s[i] == 'O')
  48.             pos.push_back({ 2, i });
  49.     }
  50.  
  51.     long long res = 0;
  52.  
  53.     for (int i = 1; i < pos.size(); i++) {
  54.         if (pos[i - 1].first == pos[i].first)
  55.             continue;
  56.  
  57.         long long l = pos[i - 1].second + 1;
  58.         long long r = s.size() - pos[i].second;
  59.  
  60.         res = (res + l * r % MOD) % MOD;
  61.     }
  62.  
  63.     return res;
  64. }
  65.  
  66. string generateString(int size, int n) {
  67.     string letters = "FOX";
  68.     string res;
  69.     for (int i = 0; i < size; i++) {
  70.         res += letters[n % 3];
  71.         n /= 3;
  72.     }
  73.     return res;
  74. }
  75.  
  76. void testG() {
  77.     for (int size = 1, limit = 3; size <= 10; size++, limit *= 3) {
  78.         for (int n = 0; n < limit; n++) {
  79.             string s = generateString(size, n);
  80.  
  81.             long long res = g(s);
  82.             long long resNaive = gNaive(s);
  83.  
  84.             if (res != resNaive) {
  85.                 cout << s << "\n";
  86.                 cout << res << "\n";
  87.                 cout << resNaive << "\n";
  88.                 return;
  89.             }
  90.         }
  91.     }
  92.  
  93.     cerr << "Max test:";
  94.     for (int i = 0; i < 5; i++) {
  95.         string s = generateString(4e6, rand() * rand());
  96.         long long res = g(s);
  97.         cerr << res << "\n";
  98.     }
  99. }
  100.  
  101. void solve(int test) {
  102.     int n;
  103.     string s;
  104.     cin >> n >> s;
  105.  
  106.     cout << "Case #" << test << ": " << g(s) << "\n";
  107. }
  108.  
  109. int main() {
  110.     freopen("input.txt", "r", stdin);
  111.     freopen("output.txt", "w", stdout);
  112.  
  113.     //testG();
  114.  
  115.     ios_base::sync_with_stdio(0);
  116.     cin.tie(0);
  117.  
  118.     int n;
  119.     cin >> n;
  120.  
  121.     for (int test = 1; test <= n; test++)
  122.         solve(test);
  123. }
RAW Paste Data