2012-09-23 20:59:00Morris

[ZJ][數學解] a534. IOI2008 Day2.1.花園問題

內容 :

    拉姆西斯(Ramesses)二世剛打勝戰回來,為了慶祝戰爭勝利,他決定建一座皇家花園。花園將由一長排的植物所組成,從他在路克索(Luxor)的皇宮一直延伸到卡納克神殿(Temple of Karnak)。而所種的植物僅由連花(lotus)及紙莎草(papyrus)二種組成,它們分別是上埃及與下埃及的象徵。

    此花園必須種植N顆植物:而且植物數必須平衡,也就是在花園的任何連續區段中蓮花與紙莎草的數量差異不能大於2

    一個花園可以用字母L(lotus)P(papyrus)所組成的字串表示。例如,當N=5時,有14種可能的平衡花園,依英文字母次序排序如下:

LLPLP, LLPPL, LPLLP,LPLPL, LPLPP, LPPLL, LPPLP, PLLPL, PLLPP, PLPLL, PLPLP, PLPPL, PPLLP,及 PPLPL。

    某一長度的所有可能平衡花園,可依英文字母次序排序,並從1開始編號。例如,當N=5時,編號12的花園是平衡花園PLPPL

    給定N棵植物及一表示平衡花園的字串,請寫一個程式計算出該平衡花園的編號,並取其除以一給定整數M的餘數

注意,M在本題中與解題無關,它只是用來簡化計算。 

輸入說明 :

程式需從標準輸入讀入下列資料:

·    第一行有一整數N,指花園中的植物的總數。

·    第二行有一整數M 

·    第三行有一N個字元的字串,由字母L(lotus)P(papyrus)組成,代表某一個平衡花園。

輸出說明 :

程式輸出一個介於0M-1的整數至標準輸出。輸出的整數是輸入的平衡花園的編號,除以M所得到的餘數。

範例輸入 :help

範例輸入157PLPPL範例輸入2	1210000LPLLPLPPLPLL

範例輸出 :

範例輸出15範例輸出239

提示 :

100%的數據滿足 

1 <= N <= 1,000,000

7 <= M <= 10,000,000

出處 :

IOI2008 Day2 第一題 (管理:david942j)



網路上有這麼一篇解答, 雖然我看不是很懂英文, 但是他給了我上面這張圖, 再加上文中零零碎碎關鍵字
我明瞭了一切, 只考慮 L 開始的話, 而且我們關注於值域 [0, 2] 的走法, 從 0 出發,
我們可以很明顯的觀察到程式碼中的遞迴公式

dp[i][j] : i 長度, j 最後停流位置

那還有一種是上下上下的情況 (ababbaabba ...), 我們可以用 2^(剩餘長度) 去表示

然後要寄算第幾個的時候, 遇到 P 的時候, 試圖將 P 換成 L 去計算 rank,
當遇到目前最低的值域 等於 目前所在的位置時, 則可以看做 dp[i][0,1,2] + 上下上下的可能,
但是這兩個會有一種交集 (ababababab ...), 必須扣掉這一種,

另外一種是差 1 的情況, 將 P 換成 L 相當於在上升一個, 就可以直接當作 dp[i][0,1,2]

相差 2 的情況就可以不理會了, 因為沒辦法替換


#include <stdio.h>
#include <stdlib.h>
#include <string.h>
char s[1000005];
int dp[1000005][3] = {};
long long Mpow(long long x, long long y, long long mod) {
    if(!y)  return 1;
    if(y&1)
        return (x*Mpow((x*x)%mod, y/2, mod))%mod;
    return Mpow((x*x)%mod, y/2, mod);
}
int main() {
    int n, m;
    int i, j;
    scanf("%d %d", &n, &m);
    scanf("%s", s);
    dp[0][0] = 1;
    for(i = 0; i <= n; i++) {
        dp[i+1][0] = dp[i][1]%m;
        dp[i+1][1] = (dp[i][0]+dp[i][2])%m;
        dp[i+1][2] = (dp[i][1])%m;
    }
    int line = 0, rk = 0, mn = 0;
    for(i = 0; i < n; i++) {
        if(s[i] == 'P') {
            if(mn == line) {
                rk += dp[n-i][0]+dp[n-i][1]+dp[n-i][2]-1;
                int tmp = (n-i)/2;
                if((n-i)%2 == 0)    tmp--;
                rk += Mpow(2, tmp, m);
            } else if(abs(mn - line) == 1) {
                rk += dp[n-i-1][0]+dp[n-i-1][1]+dp[n-i-1][2];
                rk %= m;
            }
        }
        if(s[i] == 'L') line++;
        else line--;
        if(line < mn)   mn = line;
    }
    rk++;
    printf("%d\n", rk%m);
    return 0;
}