#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[2][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;
int acu = i % 2;
int nxt = 1 - acu;
for(int minim = 0; minim <= 2; minim++) {
for(int maxim = 0; maxim <= 2; maxim++) {
/// pun l
if(maxim != 2) {
if(c == 'L') {
add(dp[nxt][max(0, minim - 1)][maxim + 1][1], dp[acu][minim][maxim][1]);
add(dp[nxt][max(0, minim - 1)][maxim + 1][0], dp[acu][minim][maxim][0]);
} else {
add(dp[nxt][max(0, minim - 1)][maxim + 1][0], dp[acu][minim][maxim][0]);
add(dp[nxt][max(0, minim - 1)][maxim + 1][0], dp[acu][minim][maxim][1]);
}
}
/// pun P
if(minim != 2) {
if(c == 'P') {
add(dp[nxt][minim + 1][max(0, maxim - 1)][1], dp[acu][minim][maxim][1]);
add(dp[nxt][minim + 1][max(0, maxim - 1)][0], dp[acu][minim][maxim][0]);
} else {
add(dp[nxt][minim + 1][max(0, maxim - 1)][0], dp[acu][minim][maxim][0]);
}
}
dp[acu][minim][maxim][0] = dp[acu][minim][maxim][1] = 0;
}
}
}
int sum = 0;
for(int minim = 0; minim <= 2; minim++) {
for(int maxim = 0; maxim <= 2; maxim++) {
add(sum, dp[n % 2][minim][maxim][0]);
add(sum, dp[n % 2][minim][maxim][1]);
}
}
cout << sum;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
324 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
316 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
228 KB |
Output is correct |
2 |
Correct |
1 ms |
232 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
320 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
320 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
344 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
328 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
28 ms |
672 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
47 ms |
700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
75 ms |
1280 KB |
Output is correct |
2 |
Correct |
71 ms |
1184 KB |
Output is correct |
3 |
Correct |
62 ms |
1188 KB |
Output is correct |