---
tags: IOI
---
# IOI2008 Day2-1 直線状の庭園 (Linear Garden)

## 問題

https://www.ioi-jp.org/ioi/2008/problems/Day2_jpn/lg_j.pdf
https://oj.uz/problem/view/IOI08_linear_garden

バランスの取れた花壇とは、`'L'`と`'P'`からなる文字列で、どの部分文字列も`'L'`と`'P'`の個数の差が 2 以下であるようなものをいいます。
長さ $N$ のバランスの取れた花壇を辞書式順序で並べたとき、 $S$ は何番目か求めてください。

## 考察

"$S$ 以下について求める" は桁DP
$i$ 文字目まで見たときに、同一視できる条件は、(`'L'` - `'P'`) の最大値・最小値・現在値 が同じとき。

よって、
dp[$i$][$j$][$k$][$l$] = $i$ 文字目まで見たとき、(`'L'` - `'P'`) の最大値が $j$, 最小値が $k$, 現在値 $l$ であり、辞書式順序で $S$ 未満の花壇の数
で $O(N)$ 定数倍重めで DP できる。

## 実装

591 ms / 1500 ms
https://oj.uz/submission/217824

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define name3(a,b,c,d,...) d
#define rep1(a) for(ll i = 0; i < a; i++)
#define rep2(i,a) for(ll i = 0; i < a; i++)
#define rep(...) name3(__VA_ARGS__, rep3, rep2, rep1)(__VA_ARGS__)
#define each(i,a) for(auto&& i : a)
 
 
ll m;
struct Modint{
    ll x = 0;
    Modint(){}
    Modint(ll a): x(a % m){}
    Modint operator+(Modint a) const { return Modint(*this) += a; }
    Modint& operator+=(Modint a){ x += a.x; if(x >= m) x -= m; return *this; }
};
int main(){
    cin.tie(nullptr);
    ios::sync_with_stdio(false);
    ll n;
    string s;
    cin >> n >> m >> s;
    Modint dp1[5][5][5] = {}, dp2[5][5][5] = {};
    dp2[2][2][2] = 1;
    bool flag = 1;
    each(c, s){
        rep(5) rep(j, 5) if(j - i < 3) rep(k, 5) if((k ^ flag) & 1 && dp1[i][j][k].x){
            if(k < 4) dp1[i][max(j, k + 1)][k + 1] += dp1[i][j][k];
            if(k) dp1[min(i, k - 1)][j][k - 1] += dp1[i][j][k];
            dp1[i][j][k] = 0;
        }
        rep(5) rep(j, 5) if(j - i < 3) rep(k, 5) if((k ^ flag) & 1 && dp2[i][j][k].x){
            if(k < 4 && c == 'P') dp2[i][max(j, k + 1)][k + 1] += dp2[i][j][k];
            if(k && c == 'P') dp1[min(i, k - 1)][j][k - 1] += dp2[i][j][k];
            if(k && c == 'L') dp2[min(i, k - 1)][j][k - 1] += dp2[i][j][k];
            dp2[i][j][k] = 0;
        }
        flag = !flag;
    }
    Modint ans = 0;
    rep(5) rep(j, 5) if(j - i < 3) rep(k, 5) ans += dp1[i][j][k];
    ans += 1;
    cout << ans.x << endl;
}