「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)$。
```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;
}
```