CF482C Solution

spdarkle · 2024-02-26 00:00:56 · 题解

一晚上切了这一道题，悲伤。

考虑设 s_i 为选出位置状态为 i 时，所有可以确定的字符串的集合。

注意到两个字符串 a,b 在选出 T 的情况下不同，当且仅当 \exist k\in T,a_k\neq b_k。

那么再考虑设 g_{i,j} 表示选出点 j 时，与 i 不同的点的集合。

    for(int i=0;i<m;i++){
        for(int j=0;j<n;j++)for(int k=0;k<n;k++)g[j][i]|=(1ll<<k)*(a[j][i]!=a[k][i]);
    }

然后我们利用 g，可以递推出 f_{i,j} 为选出状态为 j 时，与 i 不同的点的集合。

当 j\cup \lbrace i\rbrace=U 时，说明 i 与众不同，可以唯一确定。

    for(int i=0;i<n;i++){
        for(int j=1;j<(1<<m);j++){
            f[j]=f[j^(j&-j)]|g[i][lg[j&-j]];
            if(f[j]==(((1ll<<n)-1ll)^(1ll<<i)))s[j]|=1ll<<i;
        }
    }

由此我们可以 O(n2^m+n^2m) 的求出 s。

然后考虑计算答案。

首先我们计算概率系数 p_i，表示选出集合 i 的概率，这是非常容易的。

    pi[0]=1;
    for(int i=0;i<(1<<m);i++){
        int c=0;
        for(int j=0;j<m;j++)c+=(i>>j)&1;
        for(int j=0;j<m;j++)if((i>>j)&1){
            pi[i]+=pi[i^(1<<j)]/(m-c+1);
        }
    }