IOI 2008 Day 2 - Linear Garden

耶我又來更新了(# 最近開始在virtual一些IOI題 不過這禮拜都在組server 結果2008的Day 2完全是荒廢狀態 雖然在打Day 2的時候確實有錄影 不過因為太廢了連我都不忍心看下去(X) 後來整場打下來只有銅 廢到不行 這題在賽中還只拿了20分而已 也是Day 2唯一的20分(掩面) 先附個連結 [Linear Garden](https://contest.yandex.com/ioi/contest/567/problems/D/) ### 題目： 定義如果一個01序列是好的，那麼這個序列的所有連續子序列的01個數差不能超過2。 現在給你一個好的01序列，問你他是所有相同長度當中，所有的好的01序列照字典序排序之後第幾大。 字串長度$N \leq 10^6$，輸出答案模$M$，$7 \leq M \leq 10^7$。 ### 不負責題解： 一開始寫了某種不能有連續三個同樣的出現的DP，然後00100就爛掉了。 後來發現如果把0的看成-1，1的看成+1，那麼前綴和最多只能出現三種數字，這下就好辦了，因為範圍侷限在`-2~2`之間了。 不過在 virtual 的時候被某種正的做反的做字典序，然後是前綴和還是後綴和搞到快煩死(#)就拿了個暴力分20就撤了，連個完整的小測資$N \leq 40$都沒吃下來。 後來今天先寫了一下 Codeforces 再回來想這題，五分鐘左右就想到了，延續前綴和的想法，然後試著DP。 先想一下DP會長成什麼樣子。假設前綴只有`0,1,2`兩種，那麼`1`就會從`0,2`轉，`0,2`就會從`1`轉，看起來有公式可以處理掉，不過先不管。 接下來設`dp[i][j]`代表如果自由長度還剩下`i`，此時前綴是`j`的話還有幾種作法，所以可以列出類似這樣的東西： ``` al012[i][0]=al012[i-1][1]; al012[i][1]=(al012[i-1][0]+al012[i-1][2])%m; al012[i][2]=al012[i-1][1]; ``` 然後邊界條件是`dp[0][$]=1`。 另外還有`-1,0,1`跟`-2,-1,0`兩種： ``` al901[i][0]=al901[i-1][1]; al901[i][1]=(al901[i-1][0]+al901[i-1][2])%m; al901[i][2]=al901[i-1][1]; al890[i][0]=al890[i-1][1]; al890[i][1]=(al890[i-1][0]+al890[i-1][2])%m; al890[i][2]=al890[i-1][1]; ``` 也有只有`0,1`或`-1,0`的可能性，所以： ``` al01[i][0]=al01[i-1][1]; al01[i][1]=al01[i-1][0]; al90[i][0]=al90[i-1][1]; al90[i][1]=al90[i-1][0]; ``` 這樣只要在掃到`1`的時候假設這格是`0`然後看一下是否合法跟這種case會讓答案加多少就好了。 ....... 我到底在幹嘛。 上面三段看起來根本一模一樣，而且每次都是變兩倍。 下面兩個根本從頭到尾都是1。 所以最後的code其實根本超短。

int n,m;
int p2[1000006];

int main(){
    cin>>n>>m;
    string s; cin>>s;
    p2[0]=1; for(int i=1;i<=n;++i)p2[i]=(p2[i-1]<<1)%m;
    int ans=0,pre=0,mx=0,mn=0;
    for(int i=1;i<=n;++i){
        if(s[i-1]=='P'){
            int tpre=pre+1,tmx=max(mx,tpre),tmn=min(mn,tpre);
#define get(a,b) (p2[(((a)+((b)==1))>>1)])
            if(tmn>=0 && tmx<=2)(ans+=get(n-i,tpre))%=m;
            if(tmn>=-1&& tmx<=1)(ans+=get(n-i,tpre+1))%=m;
            if(tmn>=-2&& tmx<=0)(ans+=get(n-i,tpre+2))%=m;
            if(tmn>=0 && tmx<=1)--ans;
            if(tmn>=-1&& tmx<=0)--ans;
        }
        if(s[i-1]=='L')++pre; else --pre;
        mx=max(mx,pre); mn=min(mn,pre);
    }
    cout<<(ans+1+m)%m<<endl;
}

另外這題字串內容是`L`跟`P`，不過不重要。 恩.... 找機會把整份code的字體改的跟上面一樣好了。