自动搬运

查看原文

来自洛谷，原作者为

	littlebug AFO. || 女孩纸喵 > < || 喜欢天依宝宝喵 > <

搬运于2025-08-24 22:20:23，当前版本为作者最后更新于2025-08-10 08:40:10，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

天依题！

这边支持一下绫功依受呢喵~

天依是真的可爱呀 ww

---

先形式化一下题意：

令当前吃过的店铺数为「血量」。

定义一次操作为依次执行以下操作：

• 重复当前血量次，以 $p = \frac a b$ 的概率血量减少 $1$，并且血量的下限为 $0$。
• 以 $\frac {\text 当前血量} n$ 的概率血量增加 $1$。

求血量达到 $n$ 的期望操作次数。

没错，你会发现，这样好端端的一个天依题就变成了治疗之雨。

为什么要把增加放在后面呢？因为题意要求，判定是在吃完一个店铺之后立即进行的，并不包括这个时刻和下一个时刻之间的撤场事件。所以这样定义方便一点。

---

dp，令 $f_i$ 为血量为 $i$ 时血量增加到 $n$ 的期望操作次数，令 $g_{i,j}$ 为当血量为 $i$ 时，一轮操作血量减少 $j$ 的概率。

先递推 $f_i$。假设 $g_{i,j}$ 已知，那么就只需要考虑血量是否增加就可以了，显然有：

$$f_i = \sum _{j=0} ^i g_{i,j} \left( \frac {n-(i-j)} n f_{i-j+1} + \frac {i-j} n f_{i-j} \right) + 1 $$

注意到有环没法直接递推，$n \le 3000$ 没法直接搞笑，不过把系数矩阵画出来并且旋转 $180 \degree$ 后，可以发现死一个上三角矩阵但是每一行左边都多出来一个非 $0$ 数，于是每次消元只消下一行就可以了，复杂度是 $O(n^2)$ 的。

关于 $g_{i,j}$，这个是容易的，考虑把这 $i$ 个血量是否减少画成一个 $01$ 序列，那么减少 $j$ 就是出现了 $j$ 个 $1$，显然一个这样的序列出现概率是 $p^j \times (1-p)^{i-j}$；又因为总共有 $\binom i j$ 个这样的序列，所以可以得到：

$$g_{i,j} = \binom i j p^j (1-p)^{i-j}$$

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

代码为了方便，直接把 $f_0$ 省略了，因为可以发现 dp 式子中所有 $f_0$ 的系数都为 $0$，直接省略是没什么问题的。

最后要输出 $f_1 + 1$，因为根据 dp 式子稍微推一下就可以得到 $f_0 = f_1 + 1$。

---

int n;
mint p,a[N][N],f[N];

il void gauss(int n)
{
    reverse(a+1,a+n+1); rep(i,1,n) reverse(a[i]+1,a[i]+n+1);
    int r=1,mx; mint t;
    rep(j,1,n)
    {
        mx=r; rep(i,r,r+1) if(a[i][j]>0) {mx=i; break;}
        mx^r && (swap(a[mx],a[r]),1);
        t=a[r+1][j]/a[r][j];
        rep(k,r,n+1) a[r+1][k]-=t*a[r][k];
        ++r;
    }
    rpe(j,n,1)
    {
        f[n-j+1]=a[j][n+1]/a[j][j];
        rep(i,1,j-1) a[i][n+1]-=a[i][j]*f[j],a[i][j]=0;
    }
}

il void solve()
{
    read(n); {int x,y; read(x,y),p=x*ginv(y);}
    if(n==1) return write(1ll);

    mint iv=ginv(n);
    rep(i,1,n-1)
    {
        a[i][i]=-1.,a[i][n]=-1.;
        rep(j,0,i)
        {
        	i-j+1^n && (a[i][i-j+1]+=C(i,j)*fpow(p,j)*fpow(1-p,i-j)*(n-(i-j))*iv,1);
        	a[i][i-j]+=C(i,j)*fpow(p,j)*fpow(1-p,i-j)*(i-j)*iv;
        }
    }
    gauss(n-1);

    write((int)f[1]+1);
}

---

华风夏韵，洛水天依！

Tip：并不仅仅是天依题的题解里才有最后这句话哦！