题解：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)，然后注意一下枚举的顺序就好了。

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;
}