题解：P8139 [ICPC2020 WF] Sweep Stakes

· · 题解

考虑条件概率。具体地，设事件 A 表示所有点中一共有 t 个地雷，事件 B_i 表示所选点集中有 i 个地雷。根据条件概率的定义，我们要求的即为：

P(B_i\mid A)=\dfrac{P(AB_i)}{P(A)}

对于点 (i,j)，设其为地雷的概率为 p_{i,j}，构造生成函数 \left [p_{i,j}x+(1-p_{i,j})\right]。容易用分治 FFT 求出 P(A)。要求出 P(AB_i)，实际上就是要维护下面的多项式：

\prod_{i=1}^n\prod_{j=1}^m\left [p_{i,j}x+(1-p_{i,j})\right]

我们用线段树暴力维护区间卷积，合并时暴力 FFT，复杂度应该是 O(n^3\log^2n)，理论可以通过，实际上无法通过。

注意到 p_{i,j}\leq 0.2，考虑精度损失。发现有效信息越来越少，可以直接忽略低于某一精度的值。使用线段树分治并暴力撤销而不进行多项式除法，只维护有效段并暴力卷积，可以通过本题。具体地，维护两个多项式，分别存储询问子集内的点的卷积与子集外的点的卷积。

分析复杂度。打表发现，当精度取 10^{-14} 时，多项式内元素上界为 O(n^2) 个，但远远达不到，可以通过。

#include<bits/stdc++.h>
using namespace std;
using ld=double;
const int N=5e2+3;
const ld eps=1e-14;
struct Poly{
    int l,r;
    deque<ld>q;
    Poly(){l=r=0;q.push_back(1);}
    void ins(ld p){
        q.push_back(0);++r;
        for(auto it=--q.end();;--it){
            *it*=1-p;
            if(it==q.begin())break;
            *it+=*prev(it)*p;
        }
        while(l<r&&q.front()<eps)q.pop_front(),++l;
        while(l<r&&q.back()<eps)q.pop_back(),--r;
    }
    ld operator[](int i){
        if(i<l||i>r)return eps;
        return q[i-l];
    }
}now;
#define id(x,y) ((x-1)*m+y)
#define ls mid<<1
#define rs mid<<1|1
int n,m,K,q;
ld a[N*N],b[N],c[N];
ld PA;
set<int>t[N<<1];
void build(int l=1,int r=q,int p=1){
    if(l==r){
        int k,x,y;
        for(cin>>k;k--;){
            cin>>x>>y;
            t[p].insert(id(x,y));
        }
        return;
    }
    int mid=l+r>>1;
    build(l,mid,ls);
    build(mid+1,r,rs);
    for(auto x:t[ls])t[p].insert(x);
    for(auto x:t[rs])t[p].insert(x);
}
void solve(int l=1,int r=q,int p=1){
    if(l==r){
        Poly res;
        for(auto x:t[p])res.ins(a[x]);
        int len=t[p].size(),lim=min(K,len);
        if(!PA)for(int i=0;i<=lim;++i)PA+=res[i]*now[K-i];
        for(int i=0;i<=lim;++i)printf("%.10lf ",res[i]*now[K-i]/PA);
        for(int i=K+1;i<=len;++i)printf("0 ");puts("");
        return;
    }
    int mid=l+r>>1;Poly old=now;
    for(auto x:t[p])if(!t[ls].count(x))now.ins(a[x]);
    solve(l,mid,ls);now=old;
    for(auto x:t[p])if(!t[rs].count(x))now.ins(a[x]);
    solve(mid+1,r,rs);now=old;
}
int main(){
    int u,v,w,x,y,z;
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n>>m>>K>>q;if(!q)return 0;
    for(int i=1;i<=n;++i)cin>>b[i];
    for(int i=1;i<=m;++i)cin>>c[i];
    build();
    for(int i=1;i<=n;++i)
        for(int j=1;j<=m;++j){
            a[id(i,j)]=b[i]+c[j];
            if(!t[1].count(id(i,j)))
                now.ins(b[i]+c[j]);
        }
    solve();
    return 0;
}