题解归档 - cf104114C

本文由 cf-code 本地题解库自动归档；公开内容以本地 AC/验证版本为准。

• 本地编号：cf104114C
• 本地来源：problems/cf104114C/idea.md
• 题目链接：https://codeforces.com/gym/104114/problem/C
• 原始标题：cf104114C - COVID

思路

cf104114C - COVID

Prior over all infection bitsets is uniform. We condition on every group test being positive, i.e. every test has at least one infected person.

Classify each person by a bitmask mask[p] of tests they appear in (m <= 15).

For a set T of tests that fail in inclusion-exclusion, every person with mask & T != 0 must be uninfected, while people with mask & T == 0 are free. Let

cnt[T] = # people with (mask & T) == 0.

Then the denominator is:

sum_T (-1)^|T| 2^cnt[T].

For a fixed person with mask P, the numerator with that person infected only includes T disjoint from P; the person is fixed to infected, so the contribution is:

sum_{T subset complement(P)} (-1)^|T| 2^(cnt[T]-1).

The denominator is common to everyone, so sorting by that numerator is enough. Compute all cnt[T] by SOS subset sums, then all numerators by another subset zeta transform over T.

Counts can contain 2^1000, and exact ordering matters. The local toolchain here lacks Boost headers, so the submitted code uses a tiny signed big integer with only add / subtract / compare.

代码

来源：problems/cf104114C/solution.cpp

#include<bits/stdc++.h>
using namespace std;

const int BASE=1000000000;

struct Big{
    int sign=0;
    vector<int>a;

    void norm(){
        while(!a.empty()&&a.back()==0) a.pop_back();
        if(a.empty()) sign=0;
    }

    static Big one(){
        Big x;
        x.sign=1;
        x.a={1};
        return x;
    }

    static int cmp_abs(const Big&x,const Big&y){
        if(x.a.size()!=y.a.size()) return x.a.size()<y.a.size()?-1:1;
        for(int i=(int)x.a.size()-1;i>=0;i--){
            if(x.a[i]!=y.a[i]) return x.a[i]<y.a[i]?-1:1;
        }
        return 0;
    }

    static vector<int> add_abs(const vector<int>&x,const vector<int>&y){
        vector<int> z(max(x.size(),y.size())+1);
        long long carry=0;
        for(int i=0;i<(int)z.size();i++){
            long long v=carry;
            if(i<(int)x.size()) v+=x[i];
            if(i<(int)y.size()) v+=y[i];
            z[i]=v%BASE;
            carry=v/BASE;
        }
        while(!z.empty()&&z.back()==0) z.pop_back();
        return z;
    }

    static vector<int> sub_abs(const vector<int>&x,const vector<int>&y){
        vector<int> z(x.size());
        long long borrow=0;
        for(int i=0;i<(int)x.size();i++){
            long long v=(long long)x[i]-borrow-(i<(int)y.size()?y[i]:0);
            if(v<0) v+=BASE,borrow=1;
            else borrow=0;
            z[i]=v;
        }
        while(!z.empty()&&z.back()==0) z.pop_back();
        return z;
    }

    void add(const Big&o){
        if(!o.sign) return;
        if(!sign){
            *this=o;
            return;
        }
        if(sign==o.sign){
            a=add_abs(a,o.a);
            norm();
            return;
        }
        int c=cmp_abs(*this,o);
        if(c==0){
            sign=0;
            a.clear();
        }else if(c>0){
            a=sub_abs(a,o.a);
            norm();
        }else{
            a=sub_abs(o.a,a);
            sign=o.sign;
            norm();
        }
    }

    void neg(){
        sign=-sign;
    }

    static int cmp(const Big&x,const Big&y){
        if(x.sign!=y.sign) return x.sign<y.sign?-1:1;
        if(!x.sign) return 0;
        int c=cmp_abs(x,y);
        return x.sign>0?c:-c;
    }

    void mul2(){
        if(!sign) return;
        long long carry=0;
        for(int &d:a){
            long long v=2LL*d+carry;
            d=v%BASE;
            carry=v/BASE;
        }
        if(carry) a.push_back((int)carry);
    }
};

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

    int n,m;
    cin>>n>>m;
    int S=1<<m,ALL=S-1;
    vector<int> mask(n,0),freq(S,0);
    for(int i=0;i<m;i++){
        int k;
        cin>>k;
        while(k--){
            int x;
            cin>>x;
            mask[x-1]|=1<<i;
        }
    }
    for(int x:mask) freq[x]++;

    vector<int> sub=freq;
    for(int b=0;b<m;b++){
        for(int s=0;s<S;s++){
            if(s>>b&1) sub[s]+=sub[s^(1<<b)];
        }
    }

    vector<Big> pw(n+1);
    pw[0]=Big::one();
    for(int i=1;i<=n;i++){
        pw[i]=pw[i-1];
        pw[i].mul2();
    }

    vector<Big> zeta(S);
    for(int t=0;t<S;t++){
        int free_cnt=sub[ALL^t];
        if(!free_cnt) continue;
        zeta[t]=pw[free_cnt-1];
        if(__builtin_popcount((unsigned)t)&1) zeta[t].neg();
    }
    for(int b=0;b<m;b++){
        for(int s=0;s<S;s++){
            if(s>>b&1) zeta[s].add(zeta[s^(1<<b)]);
        }
    }

    vector<int> id(n);
    iota(id.begin(),id.end(),0);
    sort(id.begin(),id.end(),[&](int a,int b){
        const Big &pa=zeta[ALL^mask[a]];
        const Big &pb=zeta[ALL^mask[b]];
        int c=Big::cmp(pa,pb);
        if(c) return c<0;
        return a<b;
    });

    for(int i=0;i<n;i++){
        if(i) cout<<" ";
        cout<<id[i]+1;
    }
    cout<<"\n";
    return 0;
}