#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
ll dp[3][3][5]; //mx, mn, cur
ll ldp[3][3][5]; //mx, mn, cur
ll m;
int main()
{
int n; cin >> n; cin >> m;
string s; cin >> s;
memset(dp, 0, 3*3*5*sizeof(ll));
memset(ldp, 0, 3*3*5*sizeof(ll));
int cmx, cmn, ccur;
if(s[0] == 'P'){
dp[1][0][3] = 1;
cmx = 1, cmn = 0, ccur = 3;
}
else{
cmx = 0, cmn = 1, ccur = 1;
}
dp[0][1][1] = 1;
for (int i = 0; i < n - 1; i++)
{
swap(dp, ldp);
memset(dp, 0, 3*3*5*sizeof(ll));
for (int mx = 0; mx < 3; mx++)
for (int mn = 0; mn < 3; mn++)
for (int cur = 0; cur < 5; cur++) {
for (ll a = -1; a < 2; a += 2) {
int acur = cur - 2 + a;
int amx = max(mx, acur);
int amn = min(-mn, acur);
if(amx > 2 || amn < -2 || amx - acur > 2 || acur - amn > 2) continue;
dp[amx][-amn][acur + 2] += max(ldp[mx][mn][cur], 0LL);
dp[amx][-amn][acur + 2] %= m;
}
}
if(ccur + 1 < 5 && s[i + 1] == 'L')
dp[max(cmx, ccur - 2 + 1)][cmn][ccur + 1]--;
if(s[i + 1] == 'P') ccur++;
else ccur--;
cmx = max(ccur - 2, cmx);
cmn = max(-(ccur - 2), cmn);
}
ll res = 0;
for (int mx = 0; mx < 3; mx++)
for (int mn = 0; mn < 3; mn++)
for (int cur = 0; cur < 5; cur++){
res += dp[mx][mn][cur];
res %= m;
}
cout << res << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
344 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
512 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
344 KB |
Output is correct |
2 |
Correct |
0 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Correct |
1 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
348 KB |
Output is correct |
2 |
Incorrect |
2 ms |
348 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
348 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
616 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
26 ms |
604 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
130 ms |
1256 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
137 ms |
1344 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
189 ms |
1864 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
209 ms |
2036 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
326 ms |
3348 KB |
Output is correct |
2 |
Correct |
327 ms |
3444 KB |
Output is correct |
3 |
Correct |
319 ms |
3344 KB |
Output is correct |