题解：CF2038F Alternative Platforms

_jimmywang_

2024-11-20 20:51:43

Solution

首先把平均值换成总和除以方案数。

总所周知，\max\{a,b\}=a+b-\min\{a,b\}。

所以我们可以把原式写成：

E(b_1,b_2,\dots,b_k)=\min_{i=1}^k v[b_i]+\min_{i=1}^k r[b_i]-\min_{i=1}^k (\min\{v[b_i],r[b_i]\})

我们发现此时 v[i],r[i],\min\{v[i],r[i]\} 构成了 3 个可以独立计算的数列，我们要算的就是对于一个数列，所有大小为 k 的子集的最小值之和。

假设我们考虑的数列叫 a_1,a_2,\dots a_n。因为考虑的是子集，所以可以放心进行排序。我们先从小到大排序，并枚举最小值所在的位置。

那么所有大小为 k 的子集的最小值之和 sum_k 就等于：

\sum_{i=1}^{n-k+1}a_i\binom{n-i}{k-1}

如果你很会卷，那么你能一眼看出这玩意 FFT 一下就做完了，但是如果你不会卷，那么我们来推式子。

\begin{align}sum_k&=\sum_{i=1}^{n-k+1}a_i\binom{n-i}{k-1}\\&=\sum_{i=1}^{n-k+1}a_i\dfrac{(n-i)!}{(k-1)!(n-i-k+1)!}\\&=\dfrac{1}{(k-1)!}\sum_{i=1}^{n-k+1}\dfrac{a_i(n-i)!}{(n-i-k+1)!}\end{align}

设 F(x)=\sum_{i=1}^na_i(n-i)!x^i, G(x)=\sum_{i=0}^n\dfrac{x^i}{i!}，那么 sum_k 就等于：

\dfrac{1}{(k-1)!}[x^{n-k+1}]F \times G

然后把三个序列都做一遍并把结果相加，最后每个 sum_k 都除以 \binom{n}{k} 即可。

其实你发现每个序列独立，那么我们将这三个序列分别排序（设排完序以后 v,r,\min\{v,r\} 分别变成 A,B,C 三个序列），那么我们对 a_i=A_i+B_i-C_i 求一次 sum_k 就可以了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define f(i,a,b) for(int i=a;i<=b;++i)
#define wt int tt=d;while(tt--)
#define py puts("Yes")
#define pn puts("No")
#define fe(i,e) for(int i=0;i<e.size();i++)
#define vi vector<ll>
inline ll rd() {
    ll x=0,f=1;
    char c=getchar();
    while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}
    while(isdigit(c))x=x*10+c-'0',c=getchar();
    return x*f;
}
ll dx[4]={0,1,0,-1};
ll dy[4]={1,0,-1,0};
#define d rd()
#define pb push_back
const ll Bit=19;
const ll PoL=(1<<Bit)+5;
ll but[PoL],pw[2][PoL],Curl=-1;
void out(ll *a,ll n){f(i,0,n)printf("%lld ",a[i]);puts("");}
const ll mod=998244353,G=3,Gi=332748118;
ll qp(ll a,ll b=mod-2){ll ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;b>>=1;
    }return ans%mod;
}
namespace poly{
    ll jc[PoL+10],inv[PoL+10],inc[PoL+10];
    ll w[PoL]={1},qwq=0,Curl=-1;
    // ll usla[PoL],uslb[PoL];
    bool hpre=0;
    void pre(){
        if(hpre)return;hpre=1;
        jc[0]=jc[1]=inc[0]=inc[1]=inv[0]=inv[1]=1;
        f(i,2,PoL-1)jc[i]=jc[i-1]*i%mod,inv[i]=(mod-mod/i)*inv[mod%i]%mod,
        inc[i]=inc[i-1]*inv[i]%mod;
    }
    ll C(ll n,ll m){if(n<0||m<0||n<m)return 0;return jc[n]*inc[m]%mod*inc[n-m]%mod;}
    #define ck(x) ((x)>=mod?(x)-mod:(x))
    void revbit(ll k){
        if(Curl==k)return;Curl=k;
        f(i,0,k-1)but[i]=but[i>>1]>>1|((i&1)?(k>>1):0);
    }
    ll NTT(ll *a,ll *to,ll n,ll o){
        ll _n=1;while(_n<=n)_n<<=1;n=_n;
        revbit(n);qwq=0;
        ll inv=qp(n);

        // memcpy(to,a,sizeof(to));
        f(i,0,n-1)to[i]=a[i];
        f(i,0,n-1)if(i<but[i])swap(to[i],to[but[i]]);

        for(int l=1;l<n;l<<=1){qwq++;
            ll Wn=qp((o==1?G:Gi),((mod-1)/(l<<1)));
            for(int i=1;i<l;i++)w[i]=w[i-1]*Wn%mod;
            for(int j=0;j<n;j+=l+l){
                for(int i=0;i<l;i++){
                    int tt=w[i]*to[i|j|l]%mod;
                    to[i|j|l]=mod+to[i|j]-tt;
                    to[i|j]=to[i|j]+tt;
                }
            }if(qwq%9==0)f(i,0,n-1)to[i]%=mod;
        }if(o==1)inv=1;
        f(i,0,n-1)to[i]=to[i]*inv%mod;
        return n-1;
    }
    void Mul(ll *f,ll *g,ll *to,ll n,ll m){
        static ll _f[PoL],_g[PoL],_n,_m;_n=n,_m=m;
        f(i,0,_n)_f[i]=f[i];
        f(i,0,_m)_g[i]=g[i];
        _m+=_n,_n=1;
        _n=NTT(_f,_f,_m,1);NTT(_g,_g,_m,1);
        f(i,0,_n)to[i]=_f[i]*_g[i]%mod;
        NTT(to,to,_m,-1);
        f(i,_m+1,_n)to[i]=0;
        f(i,0,_n)_f[i]=_g[i]=0;
    }
}
using namespace poly;
ll f[PoL],g[PoL];
ll n,m;
ll a[200010],b[200010],c[200010];
ll res[200010];
int main(){
    pre();
    n=d;
    f(i,1,n)a[i]=d;f(i,1,n)b[i]=d;
    f(i,1,n)c[i]=min(a[i],b[i]);
    sort(a+1,a+n+1),sort(b+1,b+n+1),sort(c+1,c+n+1);
    f(i,1,n)a[i]+=b[i]-c[i];
    f(i,0,n)f[i]=a[i]*jc[n-i]%mod,g[i]=inc[i];
    Mul(f,g,f,n,n);
    // f(k,1,n){
    //  f(i,1,n)res[k]=(res[k]+a[i]*C(n-i,k-1))%mod;
    // }
    f(i,1,n)cout<<f[n-i+1]*inc[i-1]%mod*qp(C(n,i))%mod<<" ";
    return 0;
}