自动搬运

查看原文

来自洛谷，原作者为

	Ecrade_ 算法竞赛打 APIO，就像，只能度过一个相对失败的人生。

搬运于2025-08-24 22:29:22，当前版本为作者最后更新于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;
}