#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;
string s;
cin >> s;
dp[0][0][0][1] = 1;
for(int i = 0; i < s.size(); i++) {
char c = s[i];
for(int minim = 0; minim <= 2; minim++) {
for(int maxim = 0; maxim <= 2; 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[s.size()][minim][maxim][0]);
add(sum, dp[s.size()][minim][maxim][1]);
}
}
cout << sum;
return 0;
}
Compilation message
linear_garden.cpp: In function 'int main()':
linear_garden.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i = 0; i < s.size(); i++) {
| ~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
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 |
216 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
216 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 |
216 KB |
Output is correct |
2 |
Correct |
2 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
352 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
468 KB |
Output is correct |
2 |
Correct |
2 ms |
624 KB |
Output is correct |
3 |
Correct |
2 ms |
596 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1760 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
1888 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4704 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
5592 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
37 ms |
22548 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
29464 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
47 ms |
37340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
63 ms |
45520 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
101 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |