题解：P14805 [CCPC 2024 哈尔滨站] 弹珠赛跑

· · 题解

模拟赛出了，场切了，纪念一下。

题意是有 m 个弹珠，每一个弹珠 i 有 \frac{1}{n} 的概率通过原点的时间为 \frac{-x_j}{v_i}，求通过时间的中位数的期望。

先期望转计数，枚举每个弹珠的每个时间取值，转化为每一个时间成为中位数的方案数乘上时间值的和，再除以 n^m。

中位数可能重，为了不重不漏地计数可以在时间相同的情况下钦定一个大小顺序，这样就不会算重算漏。

这样就容易得出一个 O(nm^3) 的做法，枚举一共 m 个弹珠的 m 个取值，对剩下的所有弹珠的取值方案 DP，具体地，设 f_{i,j} 为前 i 个弹珠（默认去除了你枚举的那个弹珠，共 m-1 个），有 j 个弹珠取在了你枚举的中位数前面，这样的方案数。转移时容易的，设第 i 个弹珠有 a_i 种取值小于枚举的值，就有转移 f_{i,j}=f_{i-1,j-1}\times a_i+f_{i-1,j}\times (n-a_i)，初始时有 f_{0,0}=1，这样 f_{m-1,\frac{m-1}{2}} 就是答案。

但这样过不掉，如何优化？我们继续发觉性质：首先这个东西可以看作生成函数卷积，具体地，设 F(x) 为当前那个 DP 数组，即其 i 次项的系数为有 i 个取值小于当前中位数的方案数，那么转移就是不停地给这个多项式乘上 a_i x+(n-a_i)。其次，我们考虑将这 nm 个时间取值排序后，枚举取值时每个弹珠 a 的变化，发现只有当前的 a 会加一，其他的不变。

到这里我们几乎能推出正解了，发现每次暴力做多项式乘法是不优的，因为只有一个弹珠的多项式改变了，那咋办？我们可以继承上一个多项式，然后暴力除掉 a_i x+(n-a_i)，然后取 [x^{\frac{m-1}{2}}]F(x) 计入对答案的贡献。然后给 a_i 加一然后再乘上 a_i x+(n-a_i) 就行了。

容易做到 O(nm^2)。如果有问题可以看代码。

#include<bits/stdc++.h>
#define int long long
#define pii pair<int,int> 
#define fi first
#define se second
using namespace std;
constexpr int X=505, Mod=1e9+7;

inline bool cmp(pair<pii,int> x,pair<pii,int> y)
{
    if(x.fi.fi*y.fi.se==y.fi.fi*x.fi.se) return x.se<y.se;
    return x.fi.fi*y.fi.se<y.fi.fi*x.fi.se;
}

int N,M,x[X],v[X];
pair<pii,int> q[X*X];
int cur[X];
int F[X],res;

inline int qpow(int x,int p)
{
    int res=1;
    while(p){
        if(p&1) res=res*x%Mod;
        x=x*x%Mod; p>>=1;
    }
    return res;
}
inline void mul(int a,int b)
{
    for(int i=(M>>1);i>=0;i--) F[i]=(F[i-1]*a+F[i]*b)%Mod;
}
inline void rmul(int a,int b)
{
    int rb=qpow(b,Mod-2); F[0]=F[0]*rb%Mod;
    for(int i=1;i<=(M>>1);i++) F[i]=(F[i]-F[i-1]*a%Mod+Mod)*rb%Mod;
}

signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin>>N>>M;
    for(int i=1;i<=N;i++) cin>>x[i], x[i]=-x[i];
    for(int i=1;i<=M;i++) cin>>v[i];

    for(int i=1;i<=N;i++){
        for(int j=1;j<=M;j++){
            q[(i-1)*M+j]={{x[i],v[j]},j};
        }
    }

    sort(q+1,q+N*M+1,cmp);

    F[0]=1;
    for(int i=1;i<=M;i++) mul(0,N);

    for(int i=1;i<=N*M;i++){
        int id=q[i].se;
        int x=q[i].fi.fi, b=q[i].fi.se;
        rmul(cur[id],N-cur[id]); 
        cur[id]++;
        int t=qpow(b,Mod-2)*x%Mod;
        res=(res+F[M>>1]*t)%Mod;
        mul(cur[id],N-cur[id]);
    }

    res=res*qpow(qpow(N,M),Mod-2)%Mod;

    cout<<res;
}