Guest User

Untitled

a guest
May 10th, 2020
208
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <algorithm>
  2. #include <assert.h>
  3. #include <bitset>
  4. #include <chrono>
  5. #include <cstring>
  6. #include <functional>
  7. #include <iostream>
  8. #include <istream>
  9. #include <map>
  10. #include <numeric>
  11. #include <ostream>
  12. #include <queue>
  13. #include <set>
  14. #include <stack>
  15. #include <string>
  16. #include <unordered_map>
  17. #include <unordered_set>
  18. #include <vector>
  19.  
  20. #define endl '\n'
  21.  
  22. using namespace std;
  23.  
  24. const int S = 4;
  25.  
  26. vector<int> comb(vector<int> &a, vector<int> &b)
  27. {
  28.     vector<int> r(S);
  29.  
  30.     for (int i = 0; i < S; ++i)
  31.         r[i] = b[a[i]];
  32.  
  33.     return r;
  34. }
  35.  
  36. vector<int> mcomb(vector<vector<int>> x)
  37. {
  38.     auto r = x[0];
  39.  
  40.     for (int i = 1; i < x.size(); ++i)
  41.         r = comb(r, x[i]);
  42.  
  43.     return r;
  44. }
  45.  
  46. void print(vector<int> &a)
  47. {
  48.     for (auto x : a)
  49.         cout << x << " ";
  50.     cout << endl;
  51. }
  52.  
  53. vector<int> eye, r0, r1, r2;
  54. int p0, p1, p2;
  55.  
  56. vector<vector<int>> all;
  57. vector<vector<int>> mul;
  58. vector<int> inverse;
  59.  
  60. int find(vector<int> &a)
  61. {
  62.     for (int i = 0; i < all.size(); ++i)
  63.         if (all[i] == a)
  64.             return i;
  65.  
  66.     return -1;
  67. }
  68.  
  69. void init()
  70. {
  71.     vector<int> p(S);
  72.     iota(p.begin(), p.end(), 0);
  73.  
  74.     eye = p;
  75.  
  76.     vector<vector<int>> A0, A1, A2;
  77.  
  78.     do
  79.     {
  80.         auto pp = comb(p, p);
  81.  
  82.         if (pp == eye)
  83.             A2.push_back(p);
  84.  
  85.         if (comb(pp, p) == eye)
  86.             A0.push_back(p);
  87.  
  88.         if (pp != eye && comb(pp, pp) == eye)
  89.         {
  90.             A1.push_back(p);
  91.         }
  92.  
  93.         all.push_back(p);
  94.     } while (next_permutation(p.begin(), p.end()));
  95.  
  96.     mul = vector<vector<int>>(all.size(), vector<int>(all.size()));
  97.     inverse = vector<int>(all.size(), -1);
  98.  
  99.     for (int i = 0; i < all.size(); ++i)
  100.         for (int j = 0; j < all.size(); ++j)
  101.         {
  102.             auto x = comb(all[i], all[j]);
  103.             mul[i][j] = find(x);
  104.  
  105.             if (mul[i][j] == 0)
  106.                 inverse[i] = j;
  107.         }
  108.  
  109.     // cout << A0.size() << " " << A1.size() << " " << A2.size() << endl;
  110.  
  111.     for (auto a0 : A0)
  112.     {
  113.         if (a0 == eye)
  114.             continue;
  115.         for (auto a1 : A1)
  116.         {
  117.             if (a1 == eye)
  118.                 continue;
  119.  
  120.             if (a0 == a1)
  121.                 continue;
  122.  
  123.             for (auto a2 : A2)
  124.             {
  125.                 if (a2 == eye)
  126.                     continue;
  127.  
  128.                 if (a0 == a2)
  129.                     continue;
  130.                 if (a1 == a2)
  131.                     continue;
  132.  
  133.                 if (comb(a0, a0) != comb(a1, a2))
  134.                     continue;
  135.  
  136.                 if (mcomb({a1, a1, a1}) != comb(a2, a0))
  137.                 {
  138.                     continue;
  139.                 }
  140.  
  141.                 if (mcomb({a0, a1, a2}) != eye)
  142.                     continue;
  143.  
  144.                 r0 = a0;
  145.                 r1 = a1;
  146.                 r2 = a2;
  147.  
  148.                 p0 = find(r0);
  149.                 p1 = find(r1);
  150.                 p2 = find(r2);
  151.                 return;
  152.             }
  153.         }
  154.     }
  155. }
  156.  
  157. int main()
  158. {
  159.     ios_base::sync_with_stdio(0);
  160.     cin.tie(0);
  161.  
  162.     init();
  163.  
  164.     vector<int> P = {p0, p1, p2};
  165.  
  166.     // for (auto x : inverse)
  167.     //     cout << x << " ";
  168.     // cout << endl;
  169.  
  170.     int sz = all.size();
  171.  
  172.     // print(r0);
  173.     // print(r1);
  174.     // print(r2);
  175.  
  176.     // cout << p0 << " " << p1 << " " << p2 << endl;
  177.  
  178.     // for (int i = 0; i < sz; ++i)
  179.     // {
  180.     //     for (int j = 0; j < sz; ++j)
  181.     //     {
  182.     //         cout << mul[i][j] << " ";
  183.     //     }
  184.     //     cout << endl;
  185.     // }
  186.  
  187.     int t;
  188.     cin >> t;
  189.  
  190.     while (t--)
  191.     {
  192.         int n, m;
  193.         cin >> n >> m;
  194.         string s;
  195.         cin >> s;
  196.  
  197.         vector<int> freq(sz);
  198.         vector<long long> total(sz);
  199.  
  200.         freq[0] = 1;
  201.  
  202.         int cur = 0;
  203.  
  204.         for (auto x : s)
  205.         {
  206.             int p = P[x - '0'];
  207.             cur = mul[cur][p];
  208.  
  209.             for (int j = 0; j < sz; ++j)
  210.             {
  211.                 int interval = mul[j][cur];
  212.                 total[interval] += freq[j];
  213.             }
  214.  
  215.             freq[inverse[cur]]++;
  216.         }
  217.  
  218.         while (m--)
  219.         {
  220.             string q;
  221.             cin >> q;
  222.  
  223.             int y = 0;
  224.  
  225.             for (auto x : q)
  226.             {
  227.                 int p = P[x - '0'];
  228.                 y = mul[y][p];
  229.             }
  230.  
  231.             cout << total[y] << endl;
  232.         }
  233.     }
  234.  
  235.     return 0;
  236. }
RAW Paste Data