#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1000001;
/*
L +
P -
[0, 2]
[-1, 1]
[-2, 0]
*/
int pw[N], n, MOD;
int v[N];
int solve() {
int ans = 0;
int c = 0;
for (int i = n;i >= 1;i--) {
int idx = n - i + 1;
int now = v[idx];
if (now == 0) {
c++;
}
else {
if (c == 1) {
ans = (ans + pw[(i - 1) / 2]) % MOD;
}
c--;
}
}
return ans;
}
int main() {
cin.tie(nullptr)->sync_with_stdio(false);
cin >> n >> MOD;
int c = 0, mn = 0;
pw[0] = 1;
for (int i = 1;i <= n;i++) {
pw[i] = pw[i - 1] * 2 % MOD;
char s;
cin >> s;
if (s == 'L') v[i] = 0, c++;
else v[i] = 1, c--;
mn = min(mn, c);
}
if (mn == 0) {
cout << (solve() + 1) % MOD;
return 0;
}
if (mn == -1) {
int ans = pw[n / 2];
c = 0;
for (int i = n;i >= 1;i--) {
int now = v[n - i + 1];
if (now == 0) {
c++;
}
else {
if (c == 0) {
ans = (ans + pw[i / 2]) % MOD;
}
c--;
}
}
cout << ans;
return 0;
}
int all1 = (pw[n / 2] - 1 + MOD) % MOD;
int ans = all1;
ans = (ans + pw[(n + 1) / 2]) % MOD;
for (int i = 1;i <= n;i++) v[i] ^= 1;
cout << (ans + (all1 - solve() + MOD) % MOD) % MOD;
return 0;
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2392 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
2 |
Correct |
1 ms |
2648 KB |
Output is correct |
3 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2396 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
2516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
4700 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
7108 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
7000 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
9 ms |
7260 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
11 ms |
7256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
16 ms |
9048 KB |
Output is correct |
2 |
Correct |
18 ms |
9052 KB |
Output is correct |
3 |
Correct |
12 ms |
9052 KB |
Output is correct |