题解：CF1184D2 Parallel Universes (Hard)

wishapig · 2025-12-05 10:31:44 · 题解

题意

有 n 个石子，初始时第 k 个石子标红。接下来不断进行如下操作，设当前一共还剩 l 个石子：

以 1-\dfrac{l}{m} 的概率加入一个新的石子，这个石子可以被插入在头尾或两个相邻石子中间，有 l+1 个位置可以插入，等概率随机选择一个。
以 \dfrac{l}{m} 的概率将石子断开，分成两个部分，有 l-1 个位置可以断开，等概率随机选择一个，并删除无红色石子的那个部分。

当红色石子成为其所在石子中第一个或最后一个时结束，问最后石子个数的期望，对 10^9+7 取模。

#### 思路考虑期望 dp，设 `dp[i][j]` 表示从 “有 $i$ 个石子，第 $j$ 个标红” 的局面开始，最后的期望。对于插入/删除，分类讨论操作执行的位置，可以得到一下几种情况： - 在 $j$ 之前插入一个石子：$(1-\dfrac{i}{m})\cdot \dfrac{j}{i+1}\cdot dp[i+1][j+1]

在 j 之后插入一个石子：(1-\dfrac{i}{m})\cdot \dfrac{i+1-j}{i+1}\cdot dp[i+1][j]
在 j 之前断开：\dfrac{i}{m}\cdot\dfrac{1}{i-1}\cdot \sum_{k=1}^{j-1}dp[i-k][j-k]
在 j 之后断开：\dfrac{i}{m}\cdot \dfrac{1}{i-1}\cdot \sum_{k=1}^{i-j}dp[i-k][j]

全部写在一起，就可以得到：

\begin{aligned} dp[i][j]=&(1-\dfrac{i}{m})\cdot \dfrac{j}{i+1}\cdot dp[i+1][j+1]+(1-\dfrac{i}{m})\cdot \dfrac{i+1-j}{i+1}\cdot dp[i+1][j]\\ &+\dfrac{i}{m}\cdot\dfrac{1}{i-1}\cdot (\sum_{k=1}^{j-1}dp[i-k][j-k]+\sum_{k=1}^{i-j}dp[i-k][j]) \end{aligned}

其边界情况为 dp[i][1]=dp[i][i]=i，但直接高斯消元的话有 m^2 个变量，复杂度会达到 m^6 显然是不能接受的。

但是可以发现在上面的式子中，只有 1 种情况 j 是增大的：在 j 之前插入一个石子

那么就可以进行移项，把这一项提到前面来：

\begin{aligned} dp[i+1][j+1]=\left[(1-\dfrac{i}{m})\cdot \dfrac{j}{i+1}\right]^{-1}( &dp[i][j]-(1-\dfrac{i}{m})\cdot \dfrac{i+1-j}{i+1}\cdot dp[i+1][j]\\ &-\dfrac{i}{m}\cdot\dfrac{1}{i-1}\cdot (\sum_{k=1}^{j-1}dp[i-k][j-k]+\sum_{k=1}^{i-j}dp[i-k][j])) \end{aligned}

然后可以发现，对于所有 i\in [3,m-1],j\in [2,i-1] 的 (i,j) 对都应用这个公式，则可以按 j 从小到大的顺序，将所有 i\in [4,m],j\in [3,i-1] 的 dp[i][j] 用 dp[x][2](3\le x\le m) 的线性组合和一个常数表示出来。

再对最后一行（dp[m][] 这一行）应用原先未移项的式子，可以得到一个关于第二列 m-2 个变量的方程组，解出它即可得到所有答案，复杂度 O(m^3)。

int main(){
    scanf("%d%d%d",&n,&k,&m); Invm=fastpow(m,mod-2);
    if (k==1 || k==n) return printf("%d\n",n),0;
    for (int i=2; i<=m; i++) a[i][1][1]=i,dp[i][2][i]=1;
    for (int j=2; j<m; j++){
        pre[j][j][1]=j;
        for (int i=j+1; i<m; i++){
            int Inv=fastpow(1ll*fastpow(i+1,mod-2)*j%mod*(1+mod-1ll*Invm*i%mod)%mod,mod-2);
            int v1=(mod-1ll*(i+1-j)*fastpow(j,mod-2)%mod)%mod;
            int v2=(mod-1ll*Inv*i%mod*fastpow(m*(i-1),mod-2)%mod)%mod;
            for (int k=1; k<=m; k++){
                dp[i+1][j+1][k]=(1ll*dp[i][j][k]*Inv+1ll*dp[i+1][j][k]*v1+1ll*(a[i-1][j-1][k]+pre[i-1][j][k])*v2)%mod;
                a[i][j][k]=(a[i-1][j-1][k]+dp[i][j][k])%mod;
                pre[i][j][k]=(pre[i-1][j][k]+dp[i][j][k])%mod;
            }
        }
    }
    for (int j=2; j<m; j++){
        int I=fastpow(m-1,mod-2);
        val[j+1]=(1ll*I*(1ll*a[m-1][j-1][1]+1ll*pre[m-1][j][1]+1ll*mod)+mod-dp[m][j][1])%mod;
        for (int k=3; k<=m; k++) mat[j+1][k]=(dp[m][j][k]+1ll*I*(mod-(a[m-1][j-1][k]+pre[m-1][j][k])%mod))%mod;
    }
    for (int i=3; i<=m; i++){
        if (!mat[i][i]){
            for (int j=i+1; j<=m; j++)
                if (mat[j][i]){
                    for (int k=3; k<=m; k++) swap(mat[i][k],mat[j][k]);
                    swap(val[i],val[j]); break;
                }
        }
        int I=fastpow(mat[i][i],mod-2); val[i]=1ll*val[i]*I%mod;
        for (int j=3; j<=m; j++) mat[i][j]=1ll*mat[i][j]*I%mod;
        for (int j=3; j<=m; j++){
            if (i==j) continue;
            int p=(mod-mat[j][i])%mod; val[j]=(val[j]+1ll*p*val[i])%mod;
            for (int k=3; k<=m; k++) mat[j][k]=(mat[j][k]+1ll*p*mat[i][k])%mod;
        }
    }
    for (int j=3; j<=m; j++) ans=(ans+1ll*val[j]*dp[n][k][j])%mod;
    printf("%d\n",(ans+dp[n][k][1])%mod);
}