(IOI) 2008 Day 2 p1 Linear Garden

https://contest.yandex.com/ioi/contest/567/problems/D/

一開始想說，拿最後四個字元去DP就好，結果發現根本假解QAQ

於是，只好換個想法：我們把字串畫在座標軸上，每多一個'L'字元就往上走，每多一個'P'字串就往下走，大概像下面那樣

 可以發現，一個合法的字串，最大值跟最低值的差不能超過2！

所以，合法的字串的(最低, 最高) 的種類就只有這五種：(-2,0) , (-1,1) , (-1,0) , (0,1) , (0,2)

這樣一來，就比較好分析了！

那，要算種類數的時候，當你遇到一個P，你就要算說：如果當下選L，之前會有多少個字串！

那，接下來，因為你的種類數已經是固定的，而且，你也可以知道，當你現在在某個種類的某個位置時，之後還會有哪些字串，這樣子下去算就 okay囉~。

複雜度是 O(N)

#include <bits/stdc++.h>
using namespace std;

#define int long long

typedef pair<int,int> pii;

const int N = 1000003;

#define F first
#define S second

int n,m;

//current, type, position

bitset<N> a;

int pow2[N];

int cur_mx = 0,cur_mn = 0;

int L[6] = {0,0,-1,0,-2,-1};
int R[6] = {0,1,0,2,0,1};

int cur;

bool can(int type)
{
    return L[type] <= min(cur_mn,cur+2) && max(cur_mx,cur+2) <= R[type];
}

int ask(int type,int cur,int pos)
{
    if (type == 1 && can(1))
    {
        //(0,1)
        if (0 <= cur && cur <= 1) return 1;
    }
    else if (type == 2 &&can(2))
    {
        //(-1,0)
        if (-1 <= cur && cur <= 0) return 1;
    }
    else if (type == 3 && can(3))
    {
        //(0,2)
        if (0 <= cur && cur <= 2) return pow2[ (n-pos)/2 ];
    }
    else if (type == 4 && can(4))
    {
        //(-2,0)
        if (-2 <= cur && cur <= 0) return pow2[ (n-pos)/2 ];
    }
    else if (type == 5 && can(5))
    {
        //(-1,1)
        if (-1 <= cur && cur <= 1) return pow2[ (n-pos+1)/2 ];
    }
    return 0;
}

bool real_can(int type,int pos)
{
    return (can(type) && ask(type,cur+2,pos) != 0);
}

main ()
{
    char c;
    scanf("%lld",&n);
    scanf("%lld",&m);
    getchar();
    pow2[0] = 1;
    for (int i=1;n>=i;i++)
    {
        pow2[i] = pow2[i-1] + pow2[i-1];
        if (pow2[i] >= m) pow2[i] -= m;
    }
    for (int i=1;n>=i;i++)
    {
        c = getchar();
        if (c == 'P') a[i] = true;
    }
    int ans=0;
    cur = 0;
    for (int i=1;n>=i;i++)
    {
        if (!a[i]) ++cur;
        else --cur;
        if (a[i])
        {
            if (max(cur+2,cur_mx) - cur_mn == 1) ans += (pow2[(n-i)/2] + pow2[ (n-i+1)/2 ] - 1 + m);
            else if (max(cur+2,cur_mx) - cur_mn == 2) ans += (pow2[ (n-i)/2 ]);
            while(ans >= m) ans-=m;
        }
        cur_mx = max(cur_mx,cur);
        cur_mn = min(cur_mn,cur);
        //cout << "i = " << i << " , ans = " << ans << endl;
    }
    printf("%lld\n",(ans%m+m+1)%m);
}