题解：P15793 「1&0OI R1」灼之花

· · 题解

其实没那么麻烦。

首先是怎么说明顺序不重要。

假设我们现在已经有了最优顺序。考虑一个折线 x_1,\dots,x_n（x_i 表示 i 是否发生），设 s_i=\sum\limits_{j<i}x_j。那么显然有概率为：

\prod\limits_{x_i=1}a_ik^{s_i}\times\prod\limits_{x_i=0}(1-a_ik^{s_i})

把 1-a_ik^{s_i} 拆开，我们做的事情相当于是枚举子集：

\sum\limits_{S\in\{1,\dots,n\},x_i\le[i\in S]}(-1)^{|S|-s_{n+1}}\prod\limits_{i\in S}a_ik^{s_i}

可以发现 \prod a_i 和 \prod k^{s_i} 完全可以分开来，而其余部分也只关心 |S|。所以容易说明随意排列 a_i 根本不会对答案造成影响。

然后是怎么算答案。

首先我们容易 \mathcal O(n^2) DP 出 f_{i,j} 表示 |S|=i,s_{n+1}=j 时 (-1)^{|S|-s_{n+1}}\prod\limits_{i\in S}k^{s_i} 的和。然后设我们要问的事件是 a_p，其他事件中选 i 个的 \prod a_i 之和是 g_i，那么答案为：

\sum\limits_{i=0}^{n-1}\sum\limits_{j=0}^ia_pg_if_{i,j}k^j

多项式除法或转置原理即可 \mathcal O(n^2)。（当然如果你只是单纯猜出了上面的结论，直接 DP 也同样可以 \mathcal O(n^2)。）

cin>>n,k=read();rep(i,1,n)a[i]=read();
pk[0]=1;rep(i,1,n)pk[i]=pk[i-1]*k;
f[0][0]=1;rep(i,1,n)repn(j,i){
  f[i][j+1]+=f[i-1][j]*pk[j];
  f[i][j]-=f[i-1][j]*pk[j];
}
g[0][0]=1;rep(i,1,n)repn(j,i){
  g[i][j+1]+=g[i-1][j]*a[i];
  g[i][j]+=g[i-1][j];
}
rep(i,0,n)rep(j,0,i)h[n][i]+=f[i][j]*pk[j];
per(i,n,1)rep(j,0,i){
  h[i-1][j]+=h[i][j];
  if(j)h[i-1][j-1]+=h[i][j]*a[i];
}
rep(i,1,n){
  Z ans=0;repn(j,i)ans+=g[i-1][j]*h[i][j];
  cout<<(a[i]*ans).val()<<'\n';
}

然后这个题是可以 \mathcal O(n\log^2 n) 的。

首先我们有 \sum\limits_{j=0}^if_{i,j}k^j=\prod\limits_{j=1}^i(k^j-1)。原理大概是把 s 序列倒过来然后每次 j\to j+1 的时候乘上 k^i，容易写出递推式。

考虑只求一个答案怎么做，相当于 n-1 个一次函数相乘，我们可以分治然后 NTT 合并。容易想到可以转置原理，反过来求出一个分治区间总和为 i 时对答案的贡献，时间复杂度 \mathcal O(n\log^2 n)。

实现时可以注意一下 NTT 的转置还是 NTT。

vector<Z> F[N<<1],G[N<<1];
void dfs1(int u,int L,int R){
    if(L==R){
        F[u]={1,a[L]};
        return;
    }
    int M=L+R>>1,ls=M<<1,rs=M<<1|1;
    dfs1(ls,L,M),dfs1(rs,M+1,R);
    int w=1;while(w<=R-L+1)w<<=1;
    auto vl=F[ls],vr=F[rs];
    vl.resize(w),vr.resize(w);
    ntt(vl),ntt(vr);
    repn(i,w)vl[i]*=vr[i];intt(vl);
    vl.resize(R-L+2);F[u]=vl;
}
void dfs2(int u,int L,int R){
    if(L==R){
        cout<<(a[L]*G[u][0]).val()<<'\n';
        return;
    }
    int M=L+R>>1,ls=M<<1,rs=M<<1|1;
    int w=1;while(w<=R-L+1)w<<=1;
    G[u].resize(w);
    G[ls].resize(w),G[rs].resize(w);
    F[ls].resize(w),F[rs].resize(w);
    ntt(F[ls]),ntt(F[rs]),intt(G[u]);
    repn(i,w)G[ls][i]=G[u][i]*F[rs][i],G[rs][i]=G[u][i]*F[ls][i];
    ntt(G[ls]),ntt(G[rs]);
    G[ls].resize(M-L+2),G[rs].resize(R-M+1);
    dfs2(ls,L,M),dfs2(rs,M+1,R);
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin>>n,k=read(),H=1/read(),k*=H;rep(i,1,n)a[i]=read()*H;
    pk[0]=1;rep(i,1,n)pk[i]=pk[i-1]*k;
    f[0]=1;rep(i,1,n)f[i]=f[i-1]*(pk[i]-1);
    G[1]=vector<Z>(f,f+n+1),dfs1(1,1,n),dfs2(1,1,n);
}