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

· · 题解

Solution

upd：添加了复杂度为 O(T^2) 的做法。

有趣的题目。我做了一个多小时，感觉被狠狠地诈骗了。

根据期望的线性性，我们考虑对于每个 (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) 最后恰好合成一段的概率。

相当于：i-1 和 i 最后遇不上，j 和 j+1 最后遇不上，i 和 j 最后遇上了。因为 (i,j) 中的元素的状态不需要考虑，顺其自然——最后 i 和 j 重叠，中间的部分自然会被叠到一起去。而你想想为什么题目给你的数据范围只有 100，说明它希望你对这个东西直接暴力算，也就是记录 p_{i,j,k,w} 表示四个球的位置。转移是类似的（可以参考我的代码，因为有很多 corner case 我设了好几个数组，具体含义注释里都有的。）

复杂度 O(T^4)。由于 (i,j,k,w) 有序，所以常数不大。

我的代码写得很丑啊，不想写记忆化搜索是这样的。 /cf

#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=100+5,MOD=998244353;
int n,t=100,x[MAXN],y[MAXN];
ll f[MAXN][MAXN],ff[MAXN][MAXN],g[MAXN][MAXN][MAXN],h[MAXN][MAXN][MAXN],q[MAXN][MAXN][MAXN],z[MAXN][MAXN][MAXN][MAXN];
ll qpow(ll base,int p) {
    ll ans=1;
    while(p) {
        if(p&1) ans=ans*base%MOD;
        base=base*base%MOD,p>>=1;
    }
    return ans;
}
/*
f_{i,j} 一个人在 i，另一个人在 j，要求他们合并起来
ff_{i,j} 一个人在 i，另一个人在 j，要求他们不合并起来
g_{i,j,k} (i,j,k)，要求 (j,k) 最终合并起来，且不能遇到 i。 
h_{i,j,k} (i,j,k)，要求 (i,j) 最终合并起来，且不能被 k 追上。
q_{i,j,k} (i,j,k)，要求最终遇不上。 
z_{i,j,k,w} (i,j,k,w)，要求 (j,k) 最终合并起来，不能遇上 
*/
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>t;
    ffor(i,1,t) ff[0][i]=1;
    ll _3=qpow(3,MOD-2),_7=qpow(7,MOD-2),_15=qpow(15,MOD-2);
    ffor(i,1,t) {
        f[i][i]=1;
        ffor(j,i+1,t) {
            f[i][j]=(f[i-1][j]+f[i-1][j-1]+f[i][j-1])%MOD*_3%MOD;
            ff[i][j]=(ff[i-1][j]+ff[i-1][j-1]+ff[i][j-1])%MOD*_3%MOD;
        }
    }
    ffor(i,1,t) ffor(j,i,t) g[0][i][j]=f[i][j];
    ffor(i,1,t) ffor(j,i+1,t) {
        g[i][j][j]=ff[i][j];
        ffor(k,j+1,t) g[i][j][k]=(g[i-1][j][k]+g[i-1][j-1][k]+g[i-1][j][k-1]+g[i-1][j-1][k-1]+g[i][j-1][k]+g[i][j-1][k-1]+g[i][j][k-1])%MOD*_7%MOD;
    }
    ffor(k,1,t) h[0][0][k]=1;
    ffor(i,1,t) {
        ffor(k,i+1,t) h[i][i][k]=ff[i][k];
        ffor(j,i+1,t) ffor(k,j+1,t) h[i][j][k]=(h[i-1][j][k]+h[i-1][j-1][k]+h[i-1][j][k-1]+h[i-1][j-1][k-1]+h[i][j-1][k]+h[i][j][k-1]+h[i][j-1][k-1])%MOD*_7%MOD;
    }
    ffor(i,1,t) q[0][0][i]=1;
    ffor(i,1,t) ffor(j,i+1,t) q[0][i][j]=ff[i][j];
    ffor(i,1,t) ffor(j,i+1,t) ffor(k,j+1,t) q[i][j][k]=(q[i-1][j][k]+q[i-1][j-1][k]+q[i-1][j][k-1]+q[i-1][j-1][k-1]+q[i][j-1][k]+q[i][j][k-1]+q[i][j-1][k-1])%MOD*_7%MOD;
    ffor(w,1,t) z[0][0][0][w]=1;
    ffor(j,1,t) ffor(k,j,t) ffor(w,k+1,t) z[0][j][k][w]=h[j][k][w];
    ffor(i,1,t) {
        ffor(j,i+1,t) ffor(w,j+1,t) z[i][j][j][w]=q[i][j][w];
        ffor(j,i+1,t) ffor(k,j+1,t) ffor(w,k+1,t) {
            ll sum=0;
            ffor(o,0,1) ffor(p,0,1) ffor(q,0,1) ffor(r,0,1) sum=(sum+z[i-o][j-p][k-q][w-r])%MOD;
            z[i][j][k][w]=sum*_15%MOD;
        }
    }
    ll ans=0;
    ffor(i,1,n) cin>>x[i]>>y[i],x[i]=t-x[i];
    reverse(x+1,x+n+1),reverse(y+1,y+n+1);
    ffor(i,2,n) ffor(j,i,n-1) {
        ll mul=1;
        ffor(x,i,j) mul=mul*y[x]%MOD;
        ans=(ans+mul*z[x[i-1]][x[i]][x[j]][x[j+1]])%MOD;
    }
    ffor(i,1,1) ffor(j,1,n-1) {
        ll mul=1;
        ffor(x,i,j) mul=mul*y[x]%MOD;
        ans=(ans+mul*h[x[i]][x[j]][x[j+1]])%MOD;
    }
    ffor(i,2,n) ffor(j,n,n) {
        ll mul=1;
        ffor(x,i,j) mul=mul*y[x]%MOD;
        ans=(ans+mul*g[x[i-1]][x[i]][x[j]])%MOD;
    }
    ffor(i,1,1) ffor(j,n,n) {
        ll mul=1;
        ffor(x,i,j) mul=mul*y[x]%MOD;
        ans=(ans+mul*f[x[i]][x[j]])%MOD;
    }
    cout<<ans;
    return 0;
}

被其他题解批斗了。。因为我直接看到了 T = 100 的数据范围就直接去暴力做了。

考虑我们直接钦定 i 和 j 最后合并在一起，会把所有 i' \le i , j' \ge j 的情况全部计算进去。所以设 f_{i,j} 表示钦定 i 和 j 合并的概率，prob_{i,j} 表示最终 i 和 j 合并的概率，有

f_{i,j} = \sum_{i'=1}^i \sum_{j'=j}^n prob_{i,j}

做一遍二维差分即可，复杂度 O(T^2)。

#include<bits/stdc++.h>
#define ll long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=100+5,MOD=998244353;
int n,t=100,x[MAXN],y[MAXN];
ll f[MAXN][MAXN],prob[MAXN][MAXN];
ll qpow(ll base,int p) {
    ll ans=1;
    while(p) {
        if(p&1) ans=ans*base%MOD;
        base=base*base%MOD,p>>=1;
    }
    return ans;
}
int main() {
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    cin>>n>>t;
    ll _3=qpow(3,MOD-2);
    ffor(i,1,t) {
        f[i][i]=1;
        ffor(j,i+1,t) f[i][j]=(f[i-1][j]+f[i-1][j-1]+f[i][j-1])%MOD*_3%MOD;
    }
    ffor(i,1,n) cin>>x[i]>>y[i],x[i]=t-x[i];
    reverse(x+1,x+n+1),reverse(y+1,y+n+1);
    ffor(i,1,n) ffor(j,i,n) prob[i][j]=f[x[i]][x[j]];
    roff(i,n,1) ffor(j,i,n) prob[i][j]=(prob[i][j]-prob[i-1][j]-prob[i][j+1]+prob[i-1][j+1])%MOD;
    int ans=0;
    ffor(i,1,n) {
        ll mul=1;
        ffor(j,i,n) {
            mul=mul*y[j]%MOD;
            ans=(ans+mul*prob[i][j])%MOD;
        }
    }
    cout<<(ans%MOD+MOD)%MOD;
    return 0;
}