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

const int MOD = 1000000007; 

int CountLeft(const string &drybling, int left, int right) 
{ 
	if (left > right) 
		return 0; 

	if (left == 0 && drybling[right] == 'L') 
		return 1; 

	// jeśli lewa strona jest większa niż prawa strona 
	if (left > right) 
		return 0; 

	// jeśli lewa strona jest większa lub równa 
	if (left >= right) 
		return (drybling[right] == 'L' ? 1 : 0); 

	int count = 0; 

	// sprawdzanie, czy kontakt jest po lewej stronie 
	if (drybling[left] == 'L') 
		count++; 

	// jeśli tak, to obliczanie liczby dryblingów po lewej stronie 
	count += CountLeft(drybling, left + 1, right); 

	// obliczanie liczby dryblingów po prawej stronie 
	count += CountLeft(drybling, left, right - 1); 

	return count; 
} 

int NumFantastic(const string &drybling) 
{ 
	// obliczanie liczby lewostronnych dryblingów 
	int count = CountLeft(drybling, 0, drybling.length() - 1); 

	// obliczanie liczby dryblingów zbalansowanych 
	int balance = drybling.length() / 2; 

	// jeśli drybling jest zbalansowany, dodajemy go do wyniku 
	if (count == balance) 
		return (count + 1) % MOD; 
	else
		return count % MOD; 
} 

int main() 
{ 
	// wczytywanie liczby dryblingów 
	int n; 
	cin >> n; 

	// tworzenie tablicy ciągów 
	vector<string> dryblings; 
	for (int i = 0; i < n; i++) 
	{ 
		string s; 
		cin >> s; 
		dryblings.push_back(s); 
	} 

	// wypisywanie wyników dla każdego dryblingu 
	for (int i = 0; i < n; i++) 
	{ 
		for (int j = 0; j < n; j++) 
		{ 
			// obliczanie liczby dryblingów połączonych z dryblingiem i i j 
			string drybling = dryblings[i] + dryblings[j]; 

			// wypisywanie liczby fantastycznych dryblingów 
			cout << NumFantastic(drybling) << " "; 
		} 
		cout << endl; 
	} 

	return 0; 
}