天依题！|| solution - P6395

· · 题解

天依题！

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

天依是真的可爱呀 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：并不仅仅是天依题的题解里才有最后这句话哦！