拉姆西斯(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所得到的餘數。
範例輸入1 5 7 PLPPL 範例輸入2 12 10000 LPLLPLPPLPLL
範例輸出1 5 範例輸出2 39
100%的數據滿足
1 <= N <= 1,000,000
7 <= M <= 10,000,000| 編號 | 身分 | 題目 | 主題 | 人氣 | 發表日期 |
|
沒有發現任何「解題報告」
|
|||||