「EZEC-6」跳一跳题解

Ecrade_ · 2021-02-20 20:27:08 · 题解

P0：题外话

这题其实还可以推式子，这里也不再赘述了。

P1：题解

预处理

先用逆元把百分号处理了：a\%=\dfrac{a}{100}\equiv a\times 100^{10^9+7-2}\equiv a\times (57\times 10^7+4)\ \ \ \ \ (\bmod \ 10^9+7)

下文中为了简便，a,b 均表示经逆元处理后的 a\%,b\%。

再把特殊格处理掉。

按照题目意思，额外加到特殊格 x 的分数 y 概率为 (a+b)^{x-1}\times b，即均跳上前 x-1 个格子且跳到了第 x 个格子中心的概率。

故可以预先算出所有特殊格的期望得分之和，即 \sum\limits_{i=1}^{m}(a+b)^{x_i-1}\times b\times y_i。

\text{Subtask 1}

小 A 有 50\% 概率拿到 1 分，有 50\% 概率拿到 2 分，再加上特殊格，可得期望得分为 \dfrac{3+y_1}{2}。

时间复杂度 O(1)。

int main(){
    cin>>n>>a>>b>>m;
    if (m) cin>>x>>y;
    cout<<(3 + y) * qp(2,mod - 2) % mod;
    return 0;
}

\text{Subtask 2, 3}

深搜即可，不再赘述。

时间复杂度 O(2^n)。

void dfs(ll x,ll y,ll z){
    if (x > n) return;
    ans2 = (ans2 + y * z % mod) % mod;
    dfs(x + 1,1,z * a % mod),dfs(x + 1,(y ? 2 * y % mod : 2),z * b % mod);
}

\text{Subtask 4, 5}

除去特殊格的额外加分，令 f[i] 为第 i 个格子的期望得分。则：

f[1]=(a+b)^0\times a\times b^0\times2^0+b^1\times2^1

f[2]=(a+b)^1\times a\times b^0\times2^0+(a+b)^0\times a\times b^1\times2^1+b^2\times 2^2

f[3]=(a+b)^2\times a\times b^0\times2^0+(a+b)^1\times a\times b^1\times2^1+(a+b)^0\times a\times b^2\times2^2+b^3\times 2^3

f[4]=(a+b)^3\times a\times b^0\times2^0+(a+b)^2\times a\times b^1\times2^1+(a+b)^1\times a\times b^2\times2^2+(a+b)^0\times a\times b^3\times 2^3+b^4\times2^4

\vdots

发现每个 f[i] 的最后一项 (2b)^i 很碍事，于是我们定义 f'[i] 为 f[i]-(2b)^i 的值。

易推得 f'[i]=(a+b)\times f'[i-1]+a\times (2b)^{i-1}

进而 f 数组前 i 项和 s[i] 的递推式为 s[i]=s[i-1]+f'[i]+(2b)^i

最终答案为 s[n] 加上特殊格的期望得分，时间复杂度 O(n)。

int main(){
    n = read(),a = read(),b = read(),m = read(),init();
    for (ll i = 0;i < m;i += 1){
        x = read(),y = read();
        ans = (ans + qp(a + b,x - 1) * b % mod * y % mod) % mod;
    }
    for (ll i = 1;i <= n;i += 1){
        f[i] = ((a + b) * f[i - 1] % mod + a * bb % mod) % mod;
        bb = 2 * b * bb % mod;
        s[i] = (s[i - 1] + f[i] + bb) % mod;
    }
    cout<<(s[n] + ans) % mod;
    return 0;
}

\text{Subtask 6}

易得答案为 2^{n+1}-2 加上特殊格的期望得分，时间复杂度 O(\log n)。

\text{Subtask 7}

易得答案为 n 加上特殊格的期望得分，时间复杂度 O(1)。

\text{Subtask 8, 9}

矩阵优化下前面的递推式即可。

构造矩阵：

\begin{Bmatrix}s[0]&f[0]&2ab&2b \end{Bmatrix} \times \begin{Bmatrix}1&0&0&0 \\ 1&a+b&0&0 \\ 0&1&2b&0 \\ 1&0&0&2b\end{Bmatrix}^n=\begin{Bmatrix}s[n]&f[n]&a(2b)^{n+1}&(2b)^{n+1} \end{Bmatrix}

其中 s[0]=0,f[0]=a。

答案为 s[n] 加上特殊格的期望得分，时间复杂度为 O(\log n)。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,m,a,b,x,y,ans,hx = 57e7 + 4,mod = 1e9 + 7;
struct st{ll m[5][5];}ma,mb;
inline ll read(){
   ll s = 0,w = 1;
   char ch = getchar();
   while (ch < '0'|| ch > '9'){ if (ch == '-') w = -1; ch = getchar();}
   while (ch >= '0'&& ch <= '9') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
   return s * w;
}
ll qp(ll x,ll y){
    if (!y) return 1;
    ll p = qp(x,y / 2);
    if (y & 1) return p * p % mod * x % mod;
    return p * p % mod;
}
st calc(st a,st b){
    st res; fill(res.m[0],res.m[0] + 5 * 5,0);
    for (int i = 1;i <= 4;i += 1)
        for (int j = 1;j <= 4;j += 1)
            for (int k = 1;k <= 4;k += 1)
                res.m[i][j] = (res.m[i][j] + a.m[i][k] * b.m[k][j]) % mod;
    return res;
}
ll qpmx(ll p){
    while (p){
        if (p & 1) ma = calc(ma,mb);
        mb = calc(mb,mb),p >>= 1;
    }
    return ma.m[1][1];
}
void init(){
    a = a * hx % mod,b = b * hx % mod;
    ma.m[1][2] = a,ma.m[1][3] = a * b % mod * 2 % mod,ma.m[1][4] = 2 * b % mod;
    mb.m[1][1] = mb.m[2][1] = mb.m[4][1] = mb.m[3][2] = 1;
    mb.m[2][2] = (a + b) % mod,mb.m[3][3] = mb.m[4][4] = 2 * b % mod;
}
int main(){
    n = read(),a = read(),b = read(),m = read(),init();
    for (ll i = 0;i < m;i += 1){
        x = read(),y = read();
        ans = (ans + qp(a + b,x - 1) * b % mod * y % mod) % mod;
    }
    cout<<(qpmx(n) + ans) % mod;
    return 0;
}

「EZEC-6」跳一跳 题解

预处理