#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define all(v) v.begin(), v.end()
ll dp[100000][3][3][5]; //i, mx, mn, cur
ll m;
int main()
{
int n; cin >> n; cin >> m;
string s; cin >> s;
memset(dp, 0, 100000*3*3*5*sizeof(ll));
int cmx, cmn, ccur;
if(s[0] == 'P'){
dp[0][1][0][3] = 1;
cmx = 1, cmn = 0, ccur = 3;
}
else{
cmx = 0, cmn = 1, ccur = 1;
}
dp[0][0][1][1] = 1;
for (int i = 0; i < n - 1; i++)
{
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[i + 1][amx][-amn][acur + 2] += max(dp[i][mx][mn][cur], 0LL);
dp[i + 1][amx][-amn][acur + 2] %= m;
}
}
if(ccur + 1 < 5 && s[i + 1] == 'L')
dp[i + 1][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);
}
for (int i = n - 1; i < n; i++)
{
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[i][mx][mn][cur];
res %= m;
}
cout << res << endl;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
35416 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
35420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Incorrect |
5 ms |
35456 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
35420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
35416 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
35420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
35420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
35420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
35420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
4 ms |
35420 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
35672 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
35416 KB |
Output is correct |
2 |
Correct |
4 ms |
35508 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
35672 KB |
Output is correct |
2 |
Correct |
5 ms |
35488 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
35676 KB |
Output is correct |
2 |
Incorrect |
6 ms |
35452 KB |
Output isn't correct |
3 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
10 ms |
35672 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
12 ms |
35676 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
21 ms |
35904 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
24 ms |
35676 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
191 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
187 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
209 ms |
65540 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
204 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Runtime error |
194 ms |
65536 KB |
Execution killed with signal 9 |
2 |
Halted |
0 ms |
0 KB |
- |