「EZEC-6」跳一跳 题解

Ecrade_

2021-02-20 20:27:08

Solution

**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)$。 ```cpp 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)$。 ```cpp 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)$。 ```cpp 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)$。 ```cpp #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; } ```