[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)組成，代表某一個平衡花園。
輸出說明 ：
程式輸出一個介於0到M-1的整數至標準輸出。輸出的整數是輸入的平衡花園的編號，除以M所得到的餘數。
範例輸入 ：
範例輸入157PLPPL範例輸入2 1210000LPLLPLPPLPLL
範例輸出 ：
範例輸出15範例輸出239
提示 ：
100%的數據滿足
1 <= N <= 1,000,000
7 <= M <= 10,000,000 出處 ：
網路上有這麼一篇解答, 雖然我看不是很懂英文, 但是他給了我上面這張圖, 再加上文中零零碎碎關鍵字
我明瞭了一切, 只考慮 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;
}