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
#include <iostream>
#include <vector>
using namespace std;

int solve(string s);
bool sub(string& s, vector<int>& v, int& ls);
const int MOD = 1000000007;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin>>n;
	vector<string> v(n);
	for(int i=0; i<n; i++)
		cin>>v[i];
	for(int i=0; i<n; i++)
	{
		for(int j=0; j<n; j++)
			cout<<solve(v[i]+v[j])<<" ";
		cout<<"\n";
	}
	return 0;
}

int solve(string s)
{
	int len = s.size();
	//cout<<s<<"\n"<<len<<"\n";
	int ls = 0;
	for(int i=0; i<len; i++)
	{
		ls += s[i]=='L';
	}
	int res=0;
	ls = (2*ls<len)?ls:(len-ls);
	for(; ls>0; ls--)
	{
		//cout<<"\nHERE\n";
		vector<int> v(ls);
		for(int i=0; i<ls; i++)
			v[i] = i;
		while(v[0]==0)
		{
			int i;
			for(i=0; v[ls-1-i] == 2*ls-2-2*i && i!=ls-1; i++) ;
//			if(v[1]==2 && v[2]==3) //<---
			res = (res + sub(s, v, ls))%MOD;
			v[ls-1-i]++;
			while(i--)
				v[ls-1-i] = v[ls-2-i]+1;
		}
	}
	//cout<<"\n-----\n";
	return res;
}

bool sub(string& s, vector<int>& v, int& ls)
{
	//for(int j=0; j<ls; j++)
		//cout<<v[j]<<" ";
	//cout<<"\n\n";
	int lit=0, ind=0;
	for(int i=0; s[i]!='\0' && lit<2*ls; i++)
	{
		bool bul = (ind!=ls && (lit==v[ind])) ^ (s[i]=='P');
		ind += bul && s[i]=='L';
		lit += bul;
		//cout<<i<<"; "<<bul<<"; "<<ind<<"; "<<lit<<";\n";
	}
	//cout<<"~"<<lit<<"~";
	//cout<<"\n";
	return lit==2*ls;
}