이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;
const int N = 1e6 + 5;
int mod;
inline void sadd(int &x, int y){
if ((x += y) >= mod){
x -= mod;
}
}
inline int add(int x, int y){
if ((x += y) >= mod){
x -= mod;
}
return x;
}
inline void ssub(int &x, int y){
if ((x -= y) < 0){
x += mod;
}
}
inline int sub(int x, int y){
if ((x -= y) < 0){
x += mod;
}
return x;
}
int n;
string s;
int dp[3][N];
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("KEK.inp", "r", stdin);
// freopen("KEK.out", "w", stdout);
cin >> n >> mod;
dp[-1 + 1][0] = 1;
dp[0 + 1][0] = 1;
dp[1 + 1][0] = 1;
ForE(i, 1, n){
ForE(d, -1, 1){
if (d >= 0){
sadd(dp[d + 1][i], dp[d - 1 + 1][i - 1]);
}
if (d <= 0){
sadd(dp[d + 1][i], dp[d + 1 + 1][i - 1]);
}
}
}
cin >> s;
int d = 0, mxd = 0, mnd = 0, ans = 1;
For(i, 0, n){
if (s[i] == 'P'){
d--;
int tmxd = max(mxd, d), tmnd = min(mnd, d);
if (-2 <= tmnd and tmxd <= 0){
sadd(ans, dp[(d + 1) + 1][n - i - 1]);
}
if (-1 <= tmnd and tmxd <= 1){
sadd(ans, dp[d + 1][n - i - 1]);
}
if (0 <= tmnd and tmxd <= 2){
sadd(ans, dp[(d - 1) + 1][n - i - 1]);
}
if (-1 <= tmnd and tmxd <= 0){
ssub(ans, 1);
}
if (0 <= tmnd and tmxd <= 1){
ssub(ans, 1);
}
d++;
}
if (s[i] == 'L'){
d--;
}
else{
d++;
}
mxd = max(mxd, d);
mnd = min(mnd, d);
}
cout << ans << endl;
}
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |