#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e6+10;
const int delta = 5;
int n, mod;
// pos, dif, Max L-R, Max R-L, Prefixo/menor
// -1 -> 4
// -2 -> 3
int dp[2][5][3][3][2];
char s[maxn];
bool bad(int dif, int mx)
{
if (dif > 2 || (dif == 2 && mx > 0) || (dif == 1 && mx > 1)) return 1;
return 0;
}
void add(int &a, int &b)
{
a = (a+b)%mod;
}
void init(int cur)
{
for (int j = 0; j < 5; j++)
for (int l = 0; l < 3; l++)
for (int p = 0; p < 3; p++)
for (int m = 0; m < 2; m++)
dp[cur][j][l][p][m] = 0;
}
int main(void)
{
scanf("%d %d", &n, &mod);
for (int i = 1; i <= n; i++)
scanf(" %c", &s[i]);
if (s[1] == 'L') dp[1][1][1][0][1] = 1;
else
{
dp[1][-1+delta][0][1][1] = 1;
dp[1][1][1][0][0] = 1;
}
for (int i = 1; i < n; i++)
{
int cur = (i+1)%2, ant = i%2;
init(cur);
for (int j = 0; j < 5; j++)
{
for (int l = 0; l < 3; l++)
{
for (int p = 0; p < 3; p++)
{
for (int m = 0; m < 2; m++)
{
int dif = (j <= 2 ? j : abs(j-delta));
if (j <= 2 && bad(dif, p)) continue;
if (j > 2 && bad(dif, l)) continue;
// colocar L
if ((j > 2 && !bad(dif-1, l)) || !bad(dif+1, p))
{
int e;
if (m == 0 || s[i+1] == 'P') e = 0;
else e = 1;
if (j > 2)
{
int newdif = (j == 3 ? 4 : 0);
add(dp[cur][newdif][l][p][e], dp[ant][j][l][p][m]);
}
else
{
int newdif = dif+1, newmax = max(l, newdif);
add(dp[cur][newdif][newmax][p][e], dp[ant][j][l][p][m]);
}
}
// colocar P
if ((j > 0 && j <= 2 && !bad(dif-1, p)) || !bad(dif+1, l))
{
if (m && s[i+1] == 'L') continue;
int e = m;
if (j == 0)
{
int newdif = 4, newmax = max(p, 1);
add(dp[cur][newdif][l][newmax][e], dp[ant][j][l][p][m]);
}
else if (j <= 2)
{
int newdif = dif-1;
add(dp[cur][newdif][l][p][e], dp[ant][j][l][p][m]);
}
else
{
int newdif = 3, newmax = max(p, dif+1);
add(dp[cur][newdif][l][newmax][e], dp[ant][j][l][p][m]);
}
}
}
}
}
}
}
int ans = 0;
for (int j = 0; j < 5; j++)
for (int l = 0; l < 3; l++)
for (int p = 0; p < 3; p++)
add(ans, dp[n%2][j][l][p][0]);
ans = (ans+1)%mod;
printf("%d\n", ans);
}
Compilation message
linear_garden.cpp: In function 'int main()':
linear_garden.cpp:39:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf("%d %d", &n, &mod);
~~~~~^~~~~~~~~~~~~~~~~~~
linear_garden.cpp:42:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
scanf(" %c", &s[i]);
~~~~~^~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
256 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
3 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
3 ms |
384 KB |
Output is correct |
2 |
Correct |
4 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
5 ms |
256 KB |
Output is correct |
2 |
Correct |
7 ms |
384 KB |
Output is correct |
3 |
Correct |
6 ms |
384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
20 ms |
404 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
25 ms |
408 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
52 ms |
492 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
76 ms |
516 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
262 ms |
996 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
341 ms |
1204 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
417 ms |
1384 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
603 ms |
1604 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
859 ms |
2460 KB |
Output is correct |
2 |
Correct |
793 ms |
2460 KB |
Output is correct |
3 |
Correct |
795 ms |
2468 KB |
Output is correct |