1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
#include <iostream>
#include <regex>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <vector>

using std::string;
using std::vector;

std::unordered_map<string, int> cache;

int is_fantastic(string input) {
  int count = 0;
  for (char c : input) {
    if (c == 'L') {
      ++count;
    } else if (c == 'P') {
      if (--count < 0) {
        return false;
      }
    }
  }
  return count == 0;
}

string clean(string input) {
  std::regex trim_re("X");
  return std::regex_replace(input, trim_re, "");
}

void compute_rec(string str, int index, std::unordered_set<string> &acc) {
  if (is_fantastic(str)) {
    string c = clean(str);
    if (!c.empty() && acc.find(c) == acc.end()) {
      acc.insert(c);
    }
  }
  if (index == (int) str.length()) {
    return;
  } else {
    char was = str[index];
    str[index] = 'X';
    compute_rec(str, index + 1, acc);
    str[index] = was;
    compute_rec(str, index + 1, acc);
  }
}

int compute(string input) { 
  if (input.length() < 2) {
    return 0;
  }
  std::unordered_set<string> acc; 
  compute_rec(input, 0, acc);
  return acc.size();
}

int cached_compute(string input) {
  auto ret = cache.find(input);
  if (ret != cache.end()) {
    return ret->second;
  } else {
    int q = compute(input);
    cache.insert({input, q});
    return q;
  }
}

string canonize(string input) {
  std::regex trim_re("^P+|L+$");
  input = std::regex_replace(input, trim_re, "");
  return input;
}

int main() {
  vector<string> halfs;
  int n;
  std::cin >> n;
  for (int i = 0; i < n; ++i) {
    string buf;
    std::cin >> buf;
    halfs.push_back(buf);
  }

  for (string &left : halfs) {
    for (string &right : halfs) {
      string _case = string("").append(left).append(right);

      std::cout << cached_compute(canonize(_case)) << " ";
    }
    std::cout << "\n";
  }
  return 0;
}