题解：CF1773G Game of Questions

· · 题解

CF1773G Game of Questions

体现了一种【不合法情况一定不产生影响】的思想。注意到人数 m\le 17，先状压并设计 f_S 表示幸存者集合为 S 时 Genie 的获胜概率。转移考虑枚举子集 T 表示经过一个问题后幸存者集合 S\to T，记达成这个的问题方案数为 g_{S,T}，得到转移：

f_S=\frac{1}{n}\times\left(g_{S,\emptyset}\cdot f_S+g_{S,S}\cdot f_{S}+\sum_{T\subset S,T\ne \emptyset} g_{S,T}\cdot f_T\right)

按常规套路，把这个转移解成递推式：

f_S=\dfrac{\displaystyle\sum_{T\subset S,T\ne \emptyset} g_{S,T}\cdot f_T}{n-g_{S,\emptyset}-g_{S,S}}

但这样是否正确？注意到题目中的问题是以排列的形式呈现的，问过的问题不能再被拿出来用，所以看似我们的 g_{S,T} 并不是独立的。实则不然，排列是诈骗的，注意到如果一个问题被重复问，那么后者的情况一定是要么全会要么全不会，幸存者集合一定不会发生变化，所以在枚举子集转移时选到的问题一定不会和原问题集合重复，也即在转移中默认了排列的关系，是正确的。

还需要求出 g_{S,T}(T\subseteq S)，把每个问题会的人也压成状态 w_i，则我们要对 S\cap w_i=T 计数，考虑递推来计算，用 x 表示任意一个不在 S 中的元素，从 (S\cup \set{x}) 转移。若 x\not\in w_i，则交集不变，贡献为 g_{S\cup \set{x},T}，若 x\in w_i，则交集会增加上 x，贡献为 g_{S\cup \set{x},T\cup\set{x}}，因此我们得到 g_{S,T}=g_{S\cup \set{x},T}+g_{S\cup \set{x},T\cup\set{x}}，可以 O(3^m) 计算，结合上 O(3^m) 的 \mathrm{dp}，时间复杂度 O(3^m)。

:::info[代码]

#include <bits/stdc++.h>
#define psb push_back
#define db long double

using namespace std;

typedef pair<int,int> PII;
#define fir first
#define sec second 
const int N=17;
int m,n;
vector<PII> trans[1<<N];
inline int lowbit(int x) { return x & (-x); }
int buc[1<<N];
db f[1<<N];

int main()
{
    cin >> m >> n;
    int U=(1<<n)-1;
    for (int S=0;S<=U;S++) 
    {
        for (int T=S;;T=(T-1)&S) 
        {
            trans[S].psb({T,0});
            if (!T) break;
        }
        reverse(trans[S].begin(),trans[S].end());
    }
    for (int i=1;i<=m;i++)
    {
        string str; cin >> str;
        int S=0; for (int j=0;j<n;j++) if (str[j]=='1') S|=(1<<j);
        trans[U][S].sec++;
    }

    for (int S=U-1;~S;S--)
    {
        int x=lowbit(U^S);
        for (auto [T,w] : trans[S|x]) buc[T]=w;
        for (auto &p : trans[S]) 
        {
            int T=p.fir,w=p.sec;
            p.sec=buc[T]+buc[T|x];
        }
        for (auto [T,w] : trans[S|x]) buc[T]=0;
    }

    for (int S=1;S<=U;S++)
    {
        if (!(S&1)) continue;
        int tot=m-trans[S][0].sec-trans[S].back().sec;
        if (!tot) { f[S]=1; continue; }
        db sum=0; for (auto [T,w] : trans[S]) sum+=f[T]*w;
        f[S]=sum/tot;
    }
    printf("%.12Lf",f[U]);

    return 0;
}

:::