题解：P12293 [蓝桥杯 2024 国 Java A] 合并小球

不知道写四次方的人在干什么。

根据期望的线性性，我们考虑对于每个 $(i,j)$ 计算出最终连续段 $(i,j)$ 恰好合并成一个小球。

为了方便起见，后文将整个数轴颠倒。即，所有小球向左移动，到了 $0$ 就被拿走。小球按照横坐标从小到大排序。

我们先考虑这样一个问题：请你求出最终第 $i$ 个小球和第 $i+1$ 个小球并不被合并起来的概率。这个事情是这样的：我们只需要关注 $i$ 和 $i+1$ 的移动即可。因为如果有球撞到了 $i+1$ 上，我们默认他和 $i+1$ 合并，这样决策的主动权仍然在 $i+1$ 上，对 $i$ 同理。很容易设计出 $dp_{i,j}$ 表示一个球在 $i$ ，另一个球在 $j$ ，最终能合并到一起去的概率，转移为：
$dp_{i,j} = \frac{1}{3}(dp_{i,j-1} + dp_{i-1,j} +dp_{i-1,j-1})$
需要满足 $i<j$ 。有一些很丑陋的边界情况。

那么考虑 $(i,j)$ 最后恰好合成一段的概率。

（引用自这里）

那么如何快速计算这个恰好合成一段的概率呢？我们可以发现，我们只要容斥一下就好了。

具体而言，扣掉

(l,r+1)

和

(l-1,r)

，然后加上扣重的

(l-1,r+1)

，然后注意一下枚举的顺序就好了。

CPP

const Z inv3=Z(3).inv();
Z s[109][109],p[109][109],sum[109][109],v[109],ans=0;
int pos[109],n,T;
void solve()
{
    cin>>n>>T;
    for(int i=1;i<=T;++i)
        for(int j=1;j<=i;++j)
        {
            p[i][j]=(p[i][j-1]+p[i-1][j]+p[i-1][j-1])*inv3;
            if(j==i) p[i][j]=1;
        }
    for(int i=1;i<=n;++i)
    {
        cin>>pos[i]>>v[i];
        pos[i]=T-pos[i];
    }
    for(int i=1;i<=n;++i)
    {
        sum[i][i]=v[i];
        for(int j=i+1;j<=n;++j)
            sum[i][j]=sum[i][j-1]*v[j];
    }
    for(int i=1;i<=n;++i)
        for(int j=i;j<=n;++j)
            s[i][j]=p[pos[i]][pos[j]];
    for(int i=n;i;--i)
        for(int j=i;j<=n;++j) {
            s[i][j]+=s[i-1][j+1]-s[i][j+1]-s[i-1][j],
            ans+=s[i][j]*sum[i][j];
        }
    cout<<ans.raw()<<endl;
}

题解：P12293 [蓝桥杯 2024 国 Java A] 合并小球

文章操作

相关推荐

评论

题解：P12293 [蓝桥杯 2024 国 Java A] 合并小球