#include <bits/stdc++.h>
using namespace std;
int main() {
// freopen("main.in", "r", stdin);
// freopen(".out", "w", stdout);
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N; int M; cin >> N >> M;
string S; cin >> S;
auto nxt = [&](int st, char ch)->int {
switch (st) {
case 0: return (ch=='L'? 2 : 1);
case 1: return (ch=='L'? 2 : 3);
case 2: return (ch=='L'? 5 : 1);
case 3: return (ch=='L'? 4 : -1);
case 4: return (ch=='L'? 5 : 3);
case 5: return (ch=='L'? -1 : 4);
}
return -1;
};
vector<array<int,6>> dp(N+1);
for (int s = 0; s < 6; s++) dp[0][s] = 1 % M;
for (int len = 1; len <= N; len++) {
for (int s = 0; s < 6; s++) {
long long v = 0;
int a = nxt(s, 'L'); if (a != -1) v += dp[len-1][a];
int b = nxt(s, 'P'); if (b != -1) v += dp[len-1][b];
dp[len][s] = int(v % M);
}
}
long long ans = 1 % M;
int st = 0;
for (int i = 0; i < N; i++) {
int rem = N - i;
if (S[i] == 'P') {
int a = nxt(st, 'L');
if (a != -1) ans = (ans + dp[rem-1][a]) % M;
st = nxt(st, 'P');
} else {
st = nxt(st, 'L');
}
}
cout << (ans % M) << endl;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |