[ZJ][解] a534. IOI2008 Day2.1.花＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2012-09-23 20:59:00| 人1,098| 回0 | 上一篇 | 下一篇

[ZJ][解] a534. IOI2008 Day2.1.花

推 0 收藏 0 0 站台

容：

拉姆西斯(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所得到的。

例入： 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;
}