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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 #include using namespace std; const int mod = 1000000007; int ms = 602; vector p1, L0, L1; vector sv[3]; int xd = 0; long long ldp(vector &v, bool s) { if (s == 1) xd = 0; vector xd2(v.size() + 1 + xd), pref[3] = {xd2, xd2, xd2}; int zz = 0; // liczba - może do góry - może do dołu if (s == 1) { pref[1][0] = pref[0][0] = 1; } else { for (int i = 0; i < 3; i++) pref[i] = sv[i]; } int nw = 0; int NW2 = 60000; if (s == 0) { NW2 = 0; for (auto i : v) if (i == 0) NW2++; } int c = 0; int LM = xd; for (int j = 0; j < v.size(); j++) { if (v[j]) { for (int i = min(LM, NW2); i >= 0; i--) { pref[1][i + 1] += pref[1][i]; pref[2][i + 1] += pref[1][i]; pref[1][i + 1] %= mod; pref[2][i + 1] %= mod; pref[1][i] = 0; } LM++; } else { pref[0][0] += pref[2][1]; pref[0][0] %= mod; for (int i = 1; i <= min(LM, NW2); i++) { pref[2][i - 1] += pref[2][i]; pref[1][i - 1] += pref[2][i]; pref[2][i] = 0; pref[2][i - 1] %= mod; pref[1][i - 1] %= mod; } NW2--; } // cout << '\n'; } if (s) { for (int i = 0; i < 3; i++) sv[i] = pref[i]; xd = LM; } // cout << c << '\n'; return (pref[0][0] - 1 + mod) % mod; } int main() { ios_base::sync_with_stdio(0); int n; cin >> n; // cout << ldp(vector{1, 0})[0]; // return 0; vector s(n); vector> w; for (int i = 0; i < n; i++) cin >> s[i]; for (auto i : s) { vector t; for (auto j : i) t.push_back(j == 'L'); ms = max(ms, (int)t.size() * 2 + 2); w.push_back(t); } vector ze = {1}; int lim = 0; for (auto i : w) { lim++; // if (lim > 5) // break; ldp(i, 1); for (auto j : w) { cout << ldp(j, 0) << ' '; } cout << '\n'; } }