/**
* author: Duarte Nobrega
* created: 28.05.2020
**/
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 5;
int dp [2][5][5][3], n, MOD;
string w;
void add (int &a, int b) {
a += b;
if (a >= MOD) a -= MOD;
}
int calc (int estado, char cur, char is) {
if (estado > 0) return estado;
if (cur < is) return 1;
if (cur > is) return 2;
return 0;
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> n >> MOD >> w;
memset (dp, 0, sizeof(dp));
dp[0][2][2][0] = 1;
for (int i = 0; i < n; i++) {
for (int maior = 0; maior < 5; maior++) {
for (int menor = 0; menor <= maior; menor++) {
for (int estado = 0; estado < 3; estado++) {
// Place L
if (maior - 1 >= 0 && min (menor - 1, 1) >= 0) {
add (dp[(i + 1) & 1][maior - 1][min (menor - 1, 1)][calc (estado, 'L', w[i])], dp[i & 1][maior][menor][estado]);
}
// Place P
if (menor + 1 < 5 && max (maior + 1, 3) < 5) {
add(dp[(i + 1) & 1][max (maior + 1, 3)][menor + 1][calc (estado, 'P', w[i])], dp[i & 1][maior][menor][estado]);
}
}
}
}
memset (dp[i & 1], 0, sizeof(dp[i & 1]));
}
int res = 0;
for (int maior = 0; maior < 5; maior++) {
for (int menor = 0; menor <= maior; menor++) {
add (res, dp[n & 1][maior][menor][1]);
}
}
add(res, 1);
cout << res << '\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 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
4 ms |
384 KB |
Output is correct |
2 |
Correct |
5 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
384 KB |
Output is correct |
2 |
Correct |
6 ms |
384 KB |
Output is correct |
3 |
Correct |
6 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
18 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
13 ms |
384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
504 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
34 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
117 ms |
908 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
156 ms |
1036 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
186 ms |
916 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
234 ms |
1428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
359 ms |
1436 KB |
Output is correct |
2 |
Correct |
367 ms |
1436 KB |
Output is correct |
3 |
Correct |
366 ms |
1436 KB |
Output is correct |