CF482C Game with Strings (状压DP+期望DP)

题目大意：甲和乙玩游戏，甲给出n(n<=50)个等长的字符串(len<=20)，然后甲选出其中一个字符串，乙随机询问该字符串某一位的字符(不会重复询问一个位置)，求乙能确定该串是哪个字符串的询问次数的期望值

这题不看题解好难想......(感谢zhx和zhx两位大佬的题解)

len很小，考虑状压DP，显然我们要状压询问，要定义两个状态，f[]和num[]

1表示询问，0表示未询问

那么，我们定义f[s]表示询问状态s距离确定一个字符串所需要的期望值。

 定义tot是s状态剩余的询问的次数，那么显然因为询问剩余的每一位的概率是相等的

而一个询问并不一定能确定唯一一个字符串，可能是好几个，所以我们要处理这个询问状态能确定几个字符串，即num[s]

而num[s]并不能通过暴力枚举得到，所以我们只能通过枚举它的父集来获取它的状态

我们把字符串两两匹配，定义为s状态不能确定的串(用二进制表示哪些串不能确定)，接着我们从大到小枚举状态，每个子集都从它的父集更新，取所有的并集，其中1的数量即为num

tip1：而如果1的数量为1，该状态仍然可以确定所有的串，所以此时num是0

最后我们得到一个很玄学的方程

最后的f[0]即为答案

tip2：当n==1时，出题人貌似想告诉我们，因为不论问不问都只有一个串，所以不用问也知道是哪个......

#include <cstdio>
#include <algorithm>
#include <cstring>
#define N 55
#define maxn (1<<20)+100
#define ll long long 
#define dd double
#define seed 13131
using namespace std;

int n,m;
char str[55][22];
dd f[maxn];
ll unidf[maxn];
int num[maxn];

int main()
{
    //freopen("aa.in","r",stdin);
    scanf("%d",&n);
    if(n==1) {printf("0.0000000000\n");return 0;}
    for(int i=0;i<n;i++)
        scanf("%s",str[i]);
    m=strlen(str[1]);
    for(int i=0;i<n;i++)
        for(int j=i+1;j<n;j++)
        {
            int pos=0;
            for(int k=0;k<m;k++){
                if(str[i][k]==str[j][k])
                   pos|=(1<<k);
            }
            unidf[pos]|=(1ll<<j)|(1ll<<i);
        }
    for(int s=(1<<m)-1;s>=0;s--)
    {
        for(int i=0;i<m;i++)
            if(!(s&(1<<i))) unidf[s]|=unidf[s|(1<<i)];
        for(int j=0;j<n;j++) 
            if(unidf[s]&(1ll<<j)) num[s]+=1;
        if(num[s]==1) num[s]=0;
    }
    f[(1<<m)-1]=0;
    for(int s=(1<<m)-2;s>=0;s--)
    {
        if(!num[s]) {f[s]=0;continue;}
        int tot=0;
        for(int i=0;i<m;i++) if(!(s&(1<<i)))tot++;
        for(int i=0;i<m;i++)
        {
            if(((1<<i)&s)) continue;
            f[s]+=(f[s|(1<<i)]/(dd)tot*(dd)num[s|(1<<i)]/(dd)num[s]); 
        }
        f[s]+=1.0;
    } 
    printf("%.10lf\n",max(f[0],1.00000000000));
    return 0;
}