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
// O(n^4)  :(

#include <bits/stdc++.h>
using namespace std;

constexpr int M=1'000'000'007;
int countSub(string str)
{

    int lastL=-1;
    int lastP=-1;

    int n = str.length();

    int dp[n + 1][n+1];

    dp[0][0]=1;
    for (int i=1; i<=n; i++){
        dp[0][i] = 0; //[pozycja, wysokosc]
    }
    for (int i = 1; i <= n; i++) {



        for (int h = 0; h <= n; h++) {
            dp[i][h] = dp[i-1][h];
            if ((str[i-1]=='L') && (h>0)){
                dp[i][h]=(dp[i][h]+dp[i-1][h-1])%M;

                if (lastL!=-1){
                    dp[i][h]=(dp[i][h]+M - dp[lastL-1][h-1])%M;
                }
            }

            if ((str[i-1]=='P') && (h<n) ){
                dp[i][h]=(dp[i][h]+dp[i-1][h+1])%M;
                if (lastP!=-1){
                    dp[i][h]=(dp[i][h]+M-dp[lastP-1][h+1])%M;
                }
            }
        }
        if (str[i-1]=='L'){
            lastL=i;
        }else{
            lastP=i;
        }

    }
    return dp[n][0];
}

// Driver code
int main()
{
    int n;
    vector <string> ss;
    cin>>n;
    for (int i=0; i<n; i++){
        string s;
        cin>>s;
        ss.push_back(s);
    }

    for (int j=0; j<n; j++){
        for ( int i=0; i<n; i++){

            cout<<countSub(ss[j]+ss[i])-1<<" ";
        }
        cout<<endl;
    }

    return 0;
}