| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 1151366 | sasde | Linear Garden (IOI08_linear_garden) | C++20 | 0 ms | 0 KiB |
#include <bits/stdc++.h>
#define str string
#define task "strdel"
#define int long long
#define ii pair<int,int>
#define iii pair<int,ii>
#define iv pair<ii,ii>
#define se second
#define fi first
#define ffi fi.fi
#define sfi se.fi
#define sse se.se
#define fse fi.se
#define lt(i, c, d) for(int i = c; i <= d; ++i)
#define fl(i, c, d) for(int i = d; i >= c; --i)
#define pb push_back
#define emb emplace_back
#define emf emplace_front
#define em emplace
using namespace std;
const int N = 1e6 + 5, lg = 20;
int mod = 1e9 + 7;
mt19937 rd(chrono::steady_clock::now().time_since_epoch().count());
int Rand(int u, int v) {
return u + rd() % (v - u + 1);
}
int n, f[2][5][5][5][2], k, a[N];
string s;
void add(int &a, int b) {
a += b;
if (a >= mod) a -= mod;
}
void solve() {
cin >> n >> mod >> s;
s = " " + s;
for (int i = 1; i <= n; ++i) {
a[i] = (s[i] == 'P');
}
memset(f, 0, sizeof f);
f[0][2][2][2][0] = 1;
for (int i = 0; i < n; ++i) {
memset(f[(i + 1) % 2], 0, sizeof f[(i + 1) % 2]);
for (int cnt = 0; cnt <= 4; ++cnt) {
for (int maxx = 2; maxx <= 4; ++maxx) {
for (int minn = 0; minn <= 2; ++minn) {
for (int ok = 0; ok <= 1; ++ok) {
if (!f[i % 2][cnt][maxx][minn][ok]) continue;
int cnt1 = cnt + 1;
int maxx1 = max(maxx, cnt1);
int minn1 = min(minn, cnt1);
if (maxx1 - minn1 <= 2 && (ok || a[i + 1] >= 1)) {
add(f[(i + 1) % 2][cnt1][maxx1][minn1][ok || a[i + 1] > 1], f[i % 2][cnt][maxx][minn][ok]);
}
cnt1 = cnt - 1;
maxx1 = max(maxx, cnt1);
minn1 = min(minn, cnt1);
if (maxx1 - minn1 <= 2) {
add(f[(i + 1) % 2][cnt1][maxx1][minn1][ok || a[i + 1] > 0], f[i % 2][cnt][maxx][minn][ok]);
}
}
}
}
}
}
int ans = 0;
for (int cnt = 0; cnt <= 4; ++cnt) {
for (int maxx = 2; maxx <= 4; ++maxx) {
for (int minn = 0; minn <= 2; ++minn) {
for (int ok = 0; ok <= 1; ++ok) {
if (maxx - minn <= 2) add(ans, f[n % 2][cnt][maxx][minn][ok]);
}
}
}
}
cout << ans;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
if (fopen(task ".inp", "r")) {
freopen(task ".inp", "r", stdin);
freopen(task ".out", "w", stdout);
}
int t = 1;
while (t--) {
solve();
cout << '\n';
}
}