Problem : 250 - Linear Garden

Problem Statistics

Solved Member: 14　　Submission: 58　　User Tried: 14

Statement:

Ramesses二世剛剛獲勝歸來。為了紀念這一勝利，他決定建造一座壯觀的花園。這個花園裡的植物排成一行，從他在Luxor的宮殿直達Karnak的神廟。所種植的植物只有蓮花和紙莎草，因為它們分別代表上埃及和下埃及。

這個花園中必須有N棵植物，並且必須保持平衡，即在花園中任取一段，其中蓮花和紙莎草的棵數之差不能超過2。

花園可以被表示為由字母L（蓮花）和P（紙莎草）組成的字符串。例如，當N等於5時，有14種可能的平衡花園，按照字母排序如下：LLPLP，LLPPL，LPLLP，LPLPL，LPLPP， LPPLL，LPPLP，PLLPL，PLLPP，PLPLL，PLPLP，PLPPL，PPLLP 和PPLPL。

給定長度的所有可能的平衡花園可按字母順序排序，並從1開始編號。例如，當N等於5時，第12號花園是PLPPL。

Task:

任務寫一個程序，給定植物棵數N和一個表示平衡花園的字符串，計算該花園的序號模M的結果，其中M是一個給定的整數。

注意，在問題求解中，數值M 除了簡化計算外沒有其他的作用。

限制1 <= N <= 1,000,000， 7 <= M <= 10,000,000

評分有總分40分的測試點的N不超過40。

Input:Output:

程式從標準輸入讀入下列數據：

•第一行是整數N，說明花園中植物的數量。

•第二行是整數M。

•第三行是長度為N的由字符L或P組成的字符串，表示一個平衡的花園。

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

Sample Input:Sample Output:

Sample #1 :
5
7
PLPPL

Sample #2 :
12
10000
LPLLPLPPLPLL

Sample #1 :
5

Sample #2 :
39

Source:

IOI 2008

Problem Setter

hanhan0912

Testdata:

Test	Time	Memory	Score
0-1	1500ms	65536kb
0-2	1500ms	65536kb
1	1500ms	65536kb	3
2	1500ms	65536kb	3
3	1500ms	65536kb	3
4	1500ms	65536kb	3
5	1500ms	65536kb	4
6	1500ms	65536kb	4
7	1500ms	65536kb	4
8	1500ms	65536kb	4
9	1500ms	65536kb	4
10	1500ms	65536kb	4
11	1500ms	65536kb	4
12-1	1500ms	65536kb	5
12-2	1500ms	65536kb
13-1	1500ms	65536kb	5
13-2	1500ms	65536kb
14-1	1500ms	65536kb	5
14-2	1500ms	65536kb
15	1500ms	65536kb	5
16	1500ms	65536kb	5
17	1500ms	65536kb	5
18	1500ms	65536kb	5
19	1500ms	65536kb	5
20	1500ms	65536kb	5
21	1500ms	65536kb	5
22	1500ms	65536kb	5
23-1	1500ms	65536kb	5
23-2	1500ms	65536kb
23-3	1500ms	65536kb