「EZEC-6」跳一跳

· · 题解

Description

跳一跳规则如下：

  1. 设定一个计数器 \text{cnt}，将其初始值设置为 2。
  2. 若跳上下一个格子但没跳到其中心，加 1 分，将 \text{cnt} 重置为 2。
  3. 若跳上下一个格子且跳到了其中心，加 \text{cnt} 分，将 \text{cnt} 翻倍。
  4. 若下一个格子为特殊格 x_i 且跳到了其中心，额外加 y_i 分。
  5. 终止条件为没跳上下一个格子或者跳完了所有格子。

已知共有 n 个格子，编号 1 到 n（不包含起始格）。

小 A 跳上下一个格子但没跳到其中心的概率为 a\%，跳上下一个格子且跳到了其中心的概率为 b\%，剩余 (100-a-b)\% 为没跳上下一个格子的概率。

求他的期望得分，并对 10^9+7 取模。

Solution

转移矩阵好像还有好多种，那我就再来一种。

首先加分大致有两种：

两者之间没有太大关系，可以分开考虑。

对于第二种，只要求出跳到 x_i-1 的概率，再乘上跳到 x_i 中心的概率 b\% 和加分 y_i，就是 x_i 在规则 4 中的期望得分。显然能跳上下一个格子的概率是 (a\%+b\%)，那么跳到 x_i-1 的概率就是 (a\%+b\%)^{x_i-1}，然后更新答案 ans\gets ans+(a\%+b\%)^{x_i-1}b\%y_i。x_i 的范围很大，需要用到快速幂。

对于第一种，看看能不能找规律，设 f_n 表示第 n 个格子的期望得分：

f_1&=(a\%+2b\%) \\f_2&=(a\%+b\%)a\%\times1+a\%b\%\times2^1+(b\%)^2\times2^2 \\&=(a\%+b\%)a\%+2(a\%+2b\%)b\% \\&=(a\%+2b\%)2^1(b\%)^1+(a\%+b\%)a\% \\f_3&=(a\%+b\%)^2a\%\times1+(a\%+b\%)a\%b\%\times2^1+a\%(b\%)^2\times2^2+(b\%)^3\times2^3 \\&=(a\%+b\%)^2a\%+2(a\%+b\%)a\%b\%+2^2(a\%+2b\%)(b\%)^2 \\&=(a\%+2b\%)2^2(b\%)^2+(a\%+b\%)a\%2b\%+(a\%+b\%)^2a\% \\&\dots \end{aligned}

密密麻麻的，放在一起看：

f_1&=(a\%+2b\%) \\f_2&=(a\%+2b\%)2^1(b\%)^1+(a\%+b\%)a\% \\f_3&=(a\%+2b\%)2^2(b\%)^2+(a\%+b\%)a\%2b\%+(a\%+b\%)^2a\% \\&\dots \end{aligned}

那递推式不就是：

f_n=f_{n-1}\times2b\%+(a\%+b\%)^{n-1}a\%

然后再求一个前缀和。但是还不够：1\le n\le10^{18}。考虑矩阵快速幂优化。设 s_n 表示 \sum\limits_{i=1}^{n}f_i。（显然递推式就是 s_n=s_{n-1+f_n}）

根据上述两个式子，先构造出一个矩阵（把式子里有用的都加进去）：

\begin{bmatrix}s_n&f_{n+1}&(a\%+b\%)^{n+1}\end{bmatrix}

然后尝试构造出转移矩阵：

A=\begin{bmatrix}1&0&0\\1&2b\%&0\\0&a\%&a\%+b\%\end{bmatrix}

那么：

\begin{bmatrix}s_n&f_{n+1}&(a\%+b\%)^{n+1}\end{bmatrix}&= \begin{bmatrix}s_{n-1}&f_n&(a\%+b\%)^n\end{bmatrix}\times A\\&= \begin{bmatrix}0&a\%+2b\%&a\%+b\%\end{bmatrix}\times A^n \end{aligned}

看到这么多 a\%,b\% 相乘的同时还要取模，肯定要先把 a\%,b\% 在模 10^9+7 下的逆元求出来。

最后回过头来再看我们的这个式子：

f_n=f_{n-1}\times2b\%+(a\%+b\%)^{n-1}a\%

考虑正向推导一下：

剩下的套个模板就行。时间复杂度 \mathcal O(m\log n)

不开 long long 见祖宗！！WA 了两发，先是 n 没开，又是 x 没开。

Code

#include <iostream>
#define ll long long
using namespace std;
const int mod = 1000000007;
ll n;
int a, b, m;
ll read(){
    ll x = 0;
    bool tf = 0;
    char a = getchar();
    while(a < '0' || '9' < a) a == '-'? tf = 1: -1 ,a = getchar();
    while('0' <= a && a <= '9') x = (x << 1) + (x << 3) + (a ^ 48), a = getchar();
    return tf? -x: x;
}
void write(int x){
    if(x > 9) write(x / 10);
    putchar(x % 10 | 48);
}
struct mat{
    int a[3][3];
    mat operator *(const mat &nex){
        mat ans;
        for(int i = 0; i < 3; ++ i)
            for(int j = 0; j < 3; ++ j){
                ans.a[i][j] = 0;
                for(int k = 0; k < 3; ++ k)
                    ans.a[i][j] = (ans.a[i][j] + (ll)a[i][k] * nex.a[k][j]) % mod;
            }
        return ans;
    }
} ans, base;
void inv(int &a){
    int p = mod - 2, base = 100;
    while(p > 0){
        if(p & 1) a = (ll)a * base % mod;
        base = (ll)base * base % mod;
        p >>= 1;
    }
}
int main(){
    n = read(), a = read(), b = read();
    inv(a), inv(b);
    ans.a[0][1] = (a + (b << 1) % mod) % mod, ans.a[0][2] = (a + b) % mod;
    base.a[0][0] = 1, base.a[1][0] = 1;
    base.a[1][1] = (b << 1) % mod, base.a[2][1] = a;
    base.a[2][2] = (a + b) % mod;
    while(n > 0){
        if(n & 1) ans = ans * base;
        base = base * base;
        n >>= 1;
    }
    m = read();
    for(int i = 1; i <= m; ++ i){
        ll x = read() - 1;
        int y = read(), v = b, t = a + b;
        while(x > 0){
            if(x & 1) v = (ll)v * t % mod;
            t = (ll)t * t % mod;
            x >>= 1;
        }
        ans.a[0][0] = (ans.a[0][0] + (ll)y * v) % mod;
    }
    write(ans.a[0][0]);
    return 0;
}