Solution CF1854C

BreakPlus · 2023-07-30 22:53:22 · 题解

• 观察这一过程，相当于 n 个木块向右运动，两个木块相撞仅保留一个。

• 如果没有相撞过程，那么答案是固定的。

• 假设两个木块在距离终点 x 处相撞，那么这种情况下，答案就会减少 x。

• 一次相撞一定是原先相邻的木块相撞。否则，夹在中间的木块去哪里了呢？

• 对于两个木块 u,v，把所有关于 u,v 的操作拿出来，我们发现，不管其他木块怎么变化，u 或 v 有没有和其他木块相撞，由于题中给我们的随机性，这两个木块被抽中的概率是相等的。在所有拿出来的操作中，这两个木块被抽中的概率都是 \dfrac{1}{2}。

• 那么我们很容易针对两个木块设计一个 DP 来解决这个问题。设 f(i,j) 表示第一个木块走了 i 步，第二个木块走了 j 步的概率，当 i 与 j 的差值刚好是两个木块的距离时不再走下一步。

• 时间复杂度 \mathcal{O}(nm^2)。很容易优化，但是这个做法更加直白。

inline void add(ll &a,ll b){
    a+=b;
    if(a>=mod) a-=mod;
}
inline void Minus(ll &a,ll b){
    a-=b;
    if(a<0) a+=mod;
}
ll n,m,a[505],f[505][505];
void solve(){
    n=read(), m=read();
    ll ans = 0;
    for(ll i=1;i<=n;i++){
        a[i]=read();
        ans = (ans + m + 1 - a[i]) % mod;
    }
    ll inv2 = qpow(2, mod-2);
    for(ll i=1;i<n;i++){
        ll Dec = a[i+1] - a[i];
        memset(f,0,sizeof(f));
        f[0][0]=1; ll all = (2*m+2-a[i]-a[i+1]);
        for(ll sum=0;sum<=all;sum++){
            for(ll j=0;j<=sum && j<=m+1-a[i];j++){
                ll k = sum - j;
                if(k<=m+1-a[i+1]){
                    if(j-k==Dec){
                        Minus(ans , 1ll * (m+1-a[i]-j) * f[j][k] % mod);
                    }else{
                        ll x = 1ll * f[j][k] * inv2 % mod;
                        add(f[j][k+1], x);
                        add(f[j+1][k], x);
                    }
                }
            }
        }
    } 
    printf("%d\n", ans);
}