题解与代码 - 近似（approx）

## 分块 & bitset

把值域 $[1,m]$ 分为 $\sqrt m$ 块，每个块内使用 `bitset` 模拟操作。

期望得分 $30$ 分。

## 随机化部分分

考虑给每一个数随机一个权值，把加入和移除操作转化为异或操作，然后判断当前值是否为 $0$ 就能知道集合 $T$ 是否为空。

根据评分方式中的描述，判断正确可以获得 $30\%$ 的分数。

## 最大似然法估计

考虑对于概率 $p$，令对于任意 $i\in[1,m]$，都有 $p$ 的概率将其权值重置为 $0$，求解所得集合是否为空集。进行若干次抽样，使用 **最大似然法** 估计集合大小。

设集合大小为 $x$，有 $p_1,p_2,\cdots,p_S$ 的概率重置其权值为 $0$，在 $T$ 次抽样中有 $y$ 次集合为空的概率为

$$
\prod_{i=1}^S\left(p_i^x\right)^y\left(1-p_i^x\right)^{T-y}.
$$

（$p_i^x$ 即整个集合的权值都被重置的概率。）

取上式的对数得

$$
\sum_{i=1}^S\left[xy\ln p_i+(T-y)\ln\left(1-p_i^x\right)\right].
$$

又等价于

$$
\left(\sum_{i=1}^S y\ln p_i\right)x+\sum_{i=1}^S (T-y)\ln\left(1-p_i^x\right).
$$

易知上式是一个凸函数。根据最大似然法，三分出其极值点即为集合大小 $x$ 的近似值。

在下面的代码中，使用了 $25$ 个 $p$ 值作为概率，每个 $p$ 值进行了 $10$ 次抽样测试。测试点最长用时 $7.15$ 秒，最大平均相对误差 $1.126$。

```cpp
// 2023.10.17

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int P_COUNT=25,TEST_COUNT=10;
double P[P_COUNT],precalc[P_COUNT],precalc2[P_COUNT][1000001];
ull randull(){
    ull x=rand(),y=rand();
    return (x<<31ull)|y;
}

int n,m,q,z[1000001];
ull w[1000001];
ull noww[1000001][TEST_COUNT],val[1000001][TEST_COUNT];
vector<int> x[1000001];
int total[1000001][P_COUNT];

int main(){
    srand(time(0));
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++){
        int k,v; scanf("%d",&k);
        while(k--)scanf("%d",&v),x[i].push_back(v);
    }
    for(int i=1;i<=q;i++)scanf("%d",z+i);
    for(int i=1;i<=m;i++)w[i]=randull();
    for(int _=0;_<P_COUNT;_++){
        P[_]=_==0?1:(P[_-1]*0.55);
        precalc[_]=log(1-P[_]);
        for(int i=1;i<=m;i++)precalc2[_][i]=log(1-pow(1-P[_],i));
        memset(noww,0,sizeof noww);
        memset(val,0,sizeof val);
        if(P[_]>=0.1){
            for(int i=1;i<=m;i++)
                for(int j=0;j<TEST_COUNT;j++)
                    if(_==0||randull()%(ull)(1000000/P[_])<1000000)noww[i][j]=w[i];
        }
        else{
            int total=m*TEST_COUNT*P[_];
            while(total--){
                int id=rand()%m+1,testId=rand()%TEST_COUNT;
                if(noww[id][testId])total++;
                else noww[id][testId]=w[id];
            }
        }
        for(int i=1;i<=n;i++)
            for(int v :x[i]){
                if(v<0)for(int j=0;j<TEST_COUNT;j++)
                    val[i][j]^=noww[-v][j];
                else for(int j=0;j<TEST_COUNT;j++)
                    val[i][j]^=val[v][j];
            }
        ull current[TEST_COUNT]={};
        for(int i=1;i<=q;i++){
            for(int j=0;j<TEST_COUNT;j++)
                current[j]^=val[z[i]][j],
                total[i][_]+=current[j]!=0;
        }
    }
    for(int i=1;i<=q;i++){
        if(total[i][0]==0){
            printf("0\n");
            continue;
        }
        double tmp=0;
        for(int j=1;j<P_COUNT;j++)
            tmp+=(TEST_COUNT-total[i][j])*precalc[j];
        auto calcP=[&](double x){
            double ret=x*tmp;
            for(int j=1;j<P_COUNT;j++)ret+=total[i][j]*precalc2[j][int(x)];
            return ret;
        };
        double l=1,r=m;
        while(l<r*0.98){
            // 注意到答案在对数坐标上均匀分布
            double mid1=cbrt(l*l*r),mid2=cbrt(l*r*r);
            if(calcP(mid1)<calcP(mid2))l=mid1;
            else r=mid2;
        }
        printf("%d\n",min(m,int(sqrt(l*r))));
    }
    return 0;
}
```

近似（approx）

分块 & bitset

把值域 $[1,m]$ 分为 $\sqrt m$ 块，每个块内使用 bitset 模拟操作。

期望得分 $30$ 分。

随机化部分分

考虑给每一个数随机一个权值，把加入和移除操作转化为异或操作，然后判断当前值是否为 $0$ 就能知道集合 $T$ 是否为空。

根据评分方式中的描述，判断正确可以获得 $30\%$ 的分数。

最大似然法估计

考虑对于概率 $p$ ，令对于任意 $i\in[1,m]$ ，都有 $p$ 的概率将其权值重置为 $0$ ，求解所得集合是否为空集。进行若干次抽样，使用 最大似然法 估计集合大小。

设集合大小为 $x$ ，有 $p_1,p_2,\cdots,p_S$ 的概率重置其权值为 $0$ ，在 $T$ 次抽样中有 $y$ 次集合为空的概率为

$\prod_{i=1}^S\left(p_i^x\right)^y\left(1-p_i^x\right)^{T-y}.$

（ $p_i^x$ 即整个集合的权值都被重置的概率。）

取上式的对数得

$\sum_{i=1}^S\left[xy\ln p_i+(T-y)\ln\left(1-p_i^x\right)\right].$

又等价于

$\left(\sum_{i=1}^S y\ln p_i\right)x+\sum_{i=1}^S (T-y)\ln\left(1-p_i^x\right).$

易知上式是一个凸函数。根据最大似然法，三分出其极值点即为集合大小 $x$ 的近似值。

在下面的代码中，使用了 $25$ 个 $p$ 值作为概率，每个 $p$ 值进行了 $10$ 次抽样测试。测试点最长用时 $7.15$ 秒，最大平均相对误差 $1.126$ 。

代码

// 2023.10.17

#include<bits/stdc++.h>
using namespace std;
#define ull unsigned long long
const int P_COUNT=25,TEST_COUNT=10;
double P[P_COUNT],precalc[P_COUNT],precalc2[P_COUNT][1000001];
ull randull(){
    ull x=rand(),y=rand();
    return (x<<31ull)|y;
}

int n,m,q,z[1000001];
ull w[1000001];
ull noww[1000001][TEST_COUNT],val[1000001][TEST_COUNT];
vector<int> x[1000001];
int total[1000001][P_COUNT];

int main(){
    srand(time(0));
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++){
        int k,v; scanf("%d",&k);
        while(k--)scanf("%d",&v),x[i].push_back(v);
    }
    for(int i=1;i<=q;i++)scanf("%d",z+i);
    for(int i=1;i<=m;i++)w[i]=randull();
    for(int _=0;_<P_COUNT;_++){
        P[_]=_==0?1:(P[_-1]*0.55);
        precalc[_]=log(1-P[_]);
        for(int i=1;i<=m;i++)precalc2[_][i]=log(1-pow(1-P[_],i));
        memset(noww,0,sizeof noww);
        memset(val,0,sizeof val);
        if(P[_]>=0.1){
            for(int i=1;i<=m;i++)
                for(int j=0;j<TEST_COUNT;j++)
                    if(_==0||randull()%(ull)(1000000/P[_])<1000000)noww[i][j]=w[i];
        }
        else{
            int total=m*TEST_COUNT*P[_];
            while(total--){
                int id=rand()%m+1,testId=rand()%TEST_COUNT;
                if(noww[id][testId])total++;
                else noww[id][testId]=w[id];
            }
        }
        for(int i=1;i<=n;i++)
            for(int v :x[i]){
                if(v<0)for(int j=0;j<TEST_COUNT;j++)
                    val[i][j]^=noww[-v][j];
                else for(int j=0;j<TEST_COUNT;j++)
                    val[i][j]^=val[v][j];
            }
        ull current[TEST_COUNT]={};
        for(int i=1;i<=q;i++){
            for(int j=0;j<TEST_COUNT;j++)
                current[j]^=val[z[i]][j],
                total[i][_]+=current[j]!=0;
        }
    }
    for(int i=1;i<=q;i++){
        if(total[i][0]==0){
            printf("0\n");
            continue;
        }
        double tmp=0;
        for(int j=1;j<P_COUNT;j++)
            tmp+=(TEST_COUNT-total[i][j])*precalc[j];
        auto calcP=[&](double x){
            double ret=x*tmp;
            for(int j=1;j<P_COUNT;j++)ret+=total[i][j]*precalc2[j][int(x)];
            return ret;
        };
        double l=1,r=m;
        while(l<r*0.98){
            // 注意到答案在对数坐标上均匀分布
            double mid1=cbrt(l*l*r),mid2=cbrt(l*r*r);
            if(calcP(mid1)<calcP(mid2))l=mid1;
            else r=mid2;
        }
        printf("%d\n",min(m,int(sqrt(l*r))));
    }
    return 0;
}