这个题也可以用矩阵加速解决。
先考虑 70pts 的做法，我们设 \(f_i\) 为从 \(i\) 位置到达 \(0\) 的期望步数，并尝试用 \(f_n\) 表示出所有 \(f_i\) 并利用 \(f_0\) 解出 \(f_n\) 然后回带即可。
具体地，设 \(f_i = a \times f_n + b\)，\(f_{i-1} = c \times f_n +d\)，则由于：
\[f_i = prb \times f_{i-1} + (1 - prb) \times f_{i+1} +1 \]所以：
\[\begin{align*} f_{i+1} & = f_i - prb \times f_{i-1} - 1 \\ & = (a - prb \times c) \times f_n + (b - prb \times d + 1) \end{align*} \]直接计算出 \(f_0\) 和 \(f_n\) 的关系，然后暴力算即可，复杂度 \(O(n)\)。
怎么优化呢？
注意到上面的 \(a,b,c,d\) 和新的两个系数都是线性的关系，可以直接用矩阵加速递推，时间复杂度 \(O(\log n)\)。
#include<bits/stdc++.h>
using namespace std;
inline void rd(){}
template<typename T,typename ...U>
inline void rd(T &x,U &...args){
char ch=getchar();
T f=1;x=0;
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
x*=f;rd(args...);
}
const int mod=1e9+7,N=1e6+5;
int n,m,p,q,ip;
struct Matrix{
int m[3][3];
Matrix(){memset(m,0,sizeof m);}
Matrix(int x){
memset(m,0,sizeof m);
m[0][0]=m[1][1]=m[2][2]=x;
}
Matrix friend operator*(Matrix a,Matrix b){
Matrix c;
for(int k=0;k<3;k++)
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
(c.m[i][j]+=1ll*a.m[i][k]*b.m[k][j]%mod)%=mod;
return c;
}
};
inline int KSM(int x,int n){
int ans=1;
while(n){
if(n&1)ans=1ll*ans*x%mod;
x=1ll*x*x%mod;
n>>=1;
}
return ans;
}
inline Matrix KSM(Matrix x,int n){
if(n<0)return Matrix(0);
Matrix ans=Matrix(1);
while(n){
if(n&1)ans=ans*x;
x=x*x;
n>>=1;
}
return ans;
}
int A,B,Am,Bm,ans;
signed main(){
rd(n,m,p,q);
p=1ll*p*KSM(q,mod-2)%mod;
ip=KSM(p,mod-2);
Matrix bas,ch;
ch.m[0][0]=ip,ch.m[0][1]=1;
ch.m[1][0]=1ll*(p-1)*ip%mod;
bas.m[0][0]=bas.m[0][1]=1;
A=(bas*KSM(ch,n-1)).m[0][0];
Am=(bas*KSM(ch,n-m-1)).m[0][0];
ch.m[2][2]=1,ch.m[2][0]=(mod-ip);
bas.m[0][0]=mod-1,bas.m[0][1]=0,bas.m[0][2]=1;
B=(bas*KSM(ch,n-1)).m[0][0];
Bm=(bas*KSM(ch,n-m-1)).m[0][0];
ans=1ll*(mod-B)*KSM(A,mod-2)%mod;
if(n==m)return printf("%d\n",ans),0;
ans=(1ll*Am*ans%mod+Bm)%mod;
printf("%d\n",ans);
return 0;
}