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 <vector>
#include <string>


using namespace std;

const uint32_t M = 1'000'000'000+7;


vector<string> wczytajDane(int n)
{
    vector<string> strList;
    for (int ii=0; ii<n; ii++)
    {
        string s;
        cin>>s;
        strList.push_back(s);
    }
    return strList;
}

uint32_t liczL(string s)
{
    uint32_t licz=0;
    for (int ii=0; ii<(int)s.size(); ii++)
        if(s[ii]=='L')
            licz++;
    return licz;
}

int main()
{
    int n=0;
    cin >>n;
    vector<string> strList = wczytajDane(n);

    for (int ii=0; ii<n; ii++)
        for (int jj=0; jj<n; jj++)
        {
            string str = "."s+ strList[ii]+strList[jj]; // kropka zeby indeksowac literki od 1
            uint32_t ileL = liczL(str);

            // tablica licznosci unikalnych substringow o wartosciach od 0 do ileL
            // wartosc = liczba L - liczba P w substringu
            vector<vector<uint32_t>> tab(str.size(), vector<uint32_t>(ileL+2, 0));
            tab[0][0]=1; // pusty string
            int lastL=-1, lastP=-1;

            for (uint32_t nr=1; nr<str.size(); nr++)
            {
                if (str[nr]=='L')
                {
                    for (uint32_t val=0; val<tab[0].size(); val++)
                    {
                        if (val==0)
                            tab[nr][val] = tab[nr-1][val] %M;
                        else
                        {
                            tab[nr][val] = (tab[nr-1][val] + tab[nr-1][val-1]) %M;
                            if (lastL>-1)
                                tab[nr][val] = (tab[nr][val] - tab[lastL-1][val-1] +M)%M;
                        }
                    }
                    lastL=nr;
                }
                else // str[nr]== 'P'
                {
                    for (uint32_t val=0; val<tab[0].size()-1; val++)
                    {
                        tab[nr][val] = (tab[nr-1][val] + tab[nr-1][val+1]) %M;
                        if (lastP>-1)
                            tab[nr][val] = (tab[nr][val] - tab[lastP-1][val+1] +M)%M;
                    }
                    lastP=nr;
                }

            }

            uint32_t wynik = tab.back()[0] -1; // liczba zrownowazonych substringow (ileL=ileP) minus pusty string
            cout<<wynik<<' ';
            if (jj==n-1)
                cout<<endl;
        }


    return 0;
}