#include <iostream>
#include <vector>
#include <set>
#include <unordered_set>
#include <algorithm>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "
#pragma GCC optimize("Ofast")
using namespace std;
typedef long long ll;
typedef pair <int, int> pii;
const int bSize = 11;
const int bits = 18;
const int NMAX = 1000001;
int dp[NMAX][3][3][2];
int MOD;
void add(int &x, int val) {
x += val;
if(x >= MOD)
x -= MOD;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int n;
cin >> n >> MOD;
dp[0][0][0][1] = 1;
for(int i = 0; i < n; i++) {
char c;
cin >> c;
for(int minim = 0; minim <= 2; minim++) {
for(int maxim = 0; maxim <= 2 && maxim + minim < 4; maxim++) {
/// pun l
if(maxim != 2) {
if(c == 'L') {
add(dp[i + 1][max(0, minim - 1)][maxim + 1][1], dp[i][minim][maxim][1]);
add(dp[i + 1][max(0, minim - 1)][maxim + 1][0], dp[i][minim][maxim][0]);
} else {
add(dp[i + 1][max(0, minim - 1)][maxim + 1][0], dp[i][minim][maxim][0]);
add(dp[i + 1][max(0, minim - 1)][maxim + 1][0], dp[i][minim][maxim][1]);
}
}
/// pun P
if(minim != 2) {
if(c == 'P') {
add(dp[i + 1][minim + 1][max(0, maxim - 1)][1], dp[i][minim][maxim][1]);
add(dp[i + 1][minim + 1][max(0, maxim - 1)][0], dp[i][minim][maxim][0]);
} else {
add(dp[i + 1][minim + 1][max(0, maxim - 1)][0], dp[i][minim][maxim][0]);
}
}
}
}
}
int sum = 0;
for(int minim = 0; minim <= 2; minim++) {
for(int maxim = 0; maxim <= 2; maxim++) {
add(sum, dp[n][minim][maxim][0]);
add(sum, dp[n][minim][maxim][1]);
}
}
cout << sum;
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
264 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
340 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
1 ms |
596 KB |
Output is correct |
3 |
Correct |
1 ms |
596 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
2 ms |
1748 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
1876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
4564 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
5464 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
30 ms |
22132 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
41 ms |
28592 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
58 ms |
36300 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
59 ms |
44232 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Runtime error |
95 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |