This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define dbg(x) cerr << #x << " " << x << "\n"
int MOD;
int dp[2][2 + 2 + 1][2];
void _ (int &a, int b) {
a += b;
if (a >= MOD)
a -= MOD;
}
int main() {
ios::sync_with_stdio (false);
cin.tie (0); cout.tie (0);
int n;
string garden;
cin >> n >> MOD;
cin >> garden; garden = " " + garden;
/// -> L +1
/// -> P -1
if (garden[1] == 'L') {
dp[1][2 + 1][1] = 1; /// put L as first element
}
else {
dp[1][2 - 1][1] = 1; /// put P as first element
dp[1][2 + 1][0] = 1; /// put L as first element, now we can put anything
}
for (int i = 2; i <= n; i++) {
int cur = i & 1;
int lst = !cur;
for (int dif = -2; dif <= 2; dif++)
for (int p = 0; p < 2; p++)
dp[cur][2 + dif][p] = 0;
for (int dif = -2; dif <= 2; dif++) {
/// without prefix
if (dif > -2)
_ (dp[cur][2 + dif][0], dp[lst][2 + dif - 1][0]); /// add L
if (dif < 2)
_ (dp[cur][2 + dif][0], dp[lst][2 + dif + 1][0]); /// add P
/// with prefix
if (garden[i] == 'P') {
if (dif > -2)
_ (dp[cur][2 + dif][0], dp[lst][2 + dif - 1][1]); /// add L so we get rid of prefix
if (dif < 2)
_ (dp[cur][2 + dif][1], dp[lst][2 + dif + 1][1]); /// add P to continue prefix
}
else {
if (dif > -2)
_ (dp[cur][2 + dif][1], dp[lst][2 + dif - 1][1]); /// add L to continue prefix
}
}
}
int ans = 0;
for (int dif = -2; dif <= 2; dif++)
for (int p = 0; p < 2; p++)
_ (ans, dp[n & 1][2 + dif][p]);
cout << ans << "\n";
return 0;
}
# | 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... |