2016北京集训测试赛（十）Problem A: azelso

Solution

我们把遇到一个旗子或者是遇到一个敌人称为一个事件.

这一题思路的巧妙之处在于我们要用\(f[i]\)表示从\(i\)这个事件一直走到终点这段路程中, \(i\)到\(i + 1\)这段路只被经过一次的概率. 分类讨论:

• \(i + 1\)是一个敌人, 则\(f[i] = f[i + 1] \times p[i + 1]\)
• \(i + 1\)是一个旗子, 则

\[f[i] = f[i + 1] \\ + f[i + 1] \times (1 - f[i + 1]) \times p[i + 1] \\ + f[i + 1] \times (1 - f[i + 1]) \times p[i + 1] \times (1 - f[i + 1]) \times p[i + 1] \\ + ... \\ + f[i + 1] \times (1 - f[i + 1])^\infty \times p[i + 1]^\infty
\]

表示\(i + 1\)到\(i + 2\)这一段只被走一次的概率, 加上走过\(i + 1\)后掉回\(i + 1\), 再往后走, 再掉回\(i + 1\), 一直循环, 一直掉回\(i + 1\), 直到走到终点的概率. 上面的式子用无限和式稍微处理即可化简.

然后我们又发现一段路程的被走过的期望次数等于\(1 / p_i\), 因此就可以方便地统计总共要走的期望距离.

#include <cstdio>

#include <cctype>

namespace Zeonfai

{

    inline long long getInt()

    {

        long long a = 0, sgn = 1; char c;

        while(! isdigit(c = getchar())) if(c == '-') sgn *= -1;

        while(isdigit(c)) a = a * 10 + c - '0', c = getchar();

        return a * sgn;

    }

    inline char getChar()

    {

        char c;

        while(! isgraph(c = getchar()));

        return c;

    }

}

const long long MOD = 1e9 + 7, N = 1e5;

inline long long getInverse(long long a)

{

    long long res = 1;

    for(long long x = MOD - 2; x; a = a * a % MOD, x >>= 1) if(x & 1) res = res * a % MOD;

    return res;

}

int main()

{

    #ifndef ONLINE_JUDGE

    freopen("azelso.in", "r", stdin);

    freopen("azelso.out", "w", stdout);

    #endif

    using namespace Zeonfai;

    long long len = getInt(), n = getInt();

    static long long opt[N + 2], pos[N + 2], E[N + 2], p[N + 2];

    for(long long i = 1; i <= n; ++ i)

    {

        opt[i] = getChar() == 'F' ? 0 : 1;

        pos[i] = getInt() % MOD;

        long long a = getInt(), b = getInt(); p[i] = a * getInverse(b) % MOD;

    }

    E[n] = 1;

    for(long long i = n - 1; ~ i; -- i) E[i] = opt[i + 1] == 0 ? (E[i + 1] - p[i + 1] * E[i + 1] % MOD + p[i + 1] + MOD) % MOD : E[i + 1] * getInverse(p[i + 1]) % MOD;

    long long ans = 0; pos[0] = 0; pos[n + 1] = len;

    for(long long i = 0; i <= n; ++ i)

        ans = (ans + (pos[i + 1] - pos[i] + MOD) * E[i] % MOD) % MOD;

    // ans = (ans + len - pos[n]) % MOD;

    printf("%d\n", ans);

}