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
#include <iostream>
#include <set>

using namespace std;

const int MAX_N = 607;

int n;
long long d[MAX_N];
int len[MAX_N];

bool check(int l, long long v) {
    int cnt0 = 0;
    int cnt1 = 0;
    int unb = 0;

    if (l == 0)
        return false;

    for (int i = 0; i < l; i++) {
        if (v & (1 << i)) {
            cnt1++;
            unb++;
        } else {
            cnt0++;
            unb--;
        }

        if (unb < 0)
            return false;
    }

    if (cnt0 != cnt1)
        return false;

    return true;
}

long long count_distinct(int i, int j) {
    set<pair<int, long long> > s;
    int lenij = len[i] + len[j];
    long long dij = (d[j] << len[i]) | d[i];

    for (long long i = 0; i < (1 << lenij); i++) {
        int l = 0;
        long long v = 0;

        for (int j = 0; j < lenij; j++) {
            if (i & (1 << j)) {
                v |= ((dij & (1 << j)) > 0) << l;
                l++;
            }
        }

        if (check(l, v))
            s.insert(make_pair(l, v));
    }

    return s.size();
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    for (int i = 0; i < n; i++) {
        string s;
        cin >> s;

        for (int j = 0; j < s.size(); j++)
            d[i] |= (((s[j] == 'L') ? 1 : 0) << j);

        len[i] = s.size();
    }

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            cout << count_distinct(i, j) << ' ';
        }

        cout << '\n';
    }

    return 0;
}