#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
int MOD;
int dp[2][2 + 2 + 1][2];
void _ (int &a, int b) {
a += b;
if (a >= MOD)
a -= MOD;
}
int main() {
ios::sync_with_stdio (false);
cin.tie (0); cout.tie (0);
int n;
string garden;
cin >> n >> MOD;
cin >> garden; garden = " " + garden;
/// -> L +1
/// -> P -1
if (garden[1] == 'L') {
dp[1][2 + 1][1] = 1; /// put L as first element
}
else {
dp[1][2 - 1][1] = 1; /// put P as first element
dp[1][2 + 1][0] = 1; /// put L as first element, now we can put anything
}
for (int i = 2; i <= n; i++) {
int cur = i & 1;
int lst = !cur;
for (int dif = -2; dif <= 2; dif++)
for (int p = 0; p < 2; p++)
dp[cur][2 + dif][p] = 0;
for (int dif = -2; dif <= 2; dif++) {
/// without prefix
if (dif > -2)
_ (dp[cur][2 + dif][0], dp[lst][2 + dif - 1][0]); /// add L
if (dif < 2)
_ (dp[cur][2 + dif][0], dp[lst][2 + dif + 1][0]); /// add P
/// with prefix
if (garden[i] == 'P') {
if (dif > -2)
_ (dp[cur][2 + dif][0], dp[lst][2 + dif - 1][1]); /// add L so we get rid of prefix
if (dif < 2)
_ (dp[cur][2 + dif][1], dp[lst][2 + dif + 1][1]); /// add P to continue prefix
}
else {
if (dif > -2)
_ (dp[cur][2 + dif][1], dp[lst][2 + dif - 1][1]); /// add L to continue prefix
}
}
}
int ans = 0;
for (int dif = -2; dif <= 2; dif++)
for (int p = 0; p < 2; p++)
_ (ans, dp[n & 1][2 + dif][p]);
cout << ans << "\n";
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
4 ms |
384 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
304 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
5 ms |
384 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
384 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
7 ms |
640 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
6 ms |
560 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
15 ms |
1428 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
14 ms |
1684 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
22 ms |
1988 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
21 ms |
2332 KB |
Output isn't correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
30 ms |
3356 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |