题意
你和你的朋友玩一个游戏，游戏规则如下。
你的朋友创造 n 个长度均为 m 的不相同的字符串，然后他随机地选择其中一个。他选择这些字符串的概率是相等的，也就是说，他选择 n 个字符串中的每一个的概率是 1/n 。你想猜猜你的朋友选择了哪个字符串。
为了猜到你的朋友选择了哪个字符串，你可以问他问题，形式如下：字符串中第 ｐｏｓ 个字符是什么？当问题的答案为唯一标识字符串时，我们认为这个字符串是猜测的。在字符串被猜测后，你将停止提问。
你没有一个特殊的策略，所以你每次可能会等概率的问任何一个你从没提过的位置。你的任务是确定你猜到你的朋友选的字符串所需次数的期望。
输入格式
第一行包括一个数字 ｎ 。接下来 ｎ 行，每行一个字符串，表示你朋友创造出的字符串。除此之外，所有字符的长度是相同的，在１~２０之间。
输出格式
输出期望。答案保留九位小数。误差在(10^-9)以内.
输入输出样例
输入样例#1：
2
aab
aac
输出样例#1：
2.000000000000000
输入样例#2：
3
aaA
aBa
Caa
输出样例#2：
1.666666666666667
输入样例#3：
3
aca
vac
wqq
输出样例#3：
1.000000000000000
搞了一上午
撞鸭 + 期望
我们预处理出unf[i]表示在状态为i的情况下有哪些串是符合的
unf[i]我们可以通过枚举两个串来计算他们相同的位置
然后我们再从大到小更新unf
我们还可以求出来Num[i]表示在状态为i的情况下有多少串是符合的
f[i] 表示状态为i时距离确定的期望
然后就可以从后向前转移了
状态转移方程(f[i] = sum_{j = 1 && (! i | (1 << (j - 1)))}^{n}{frac{f[i]|1<<(j-1)]}{tot} * frac{Num[i]|1<<(j-1)}{Num[i]}} + 1)
tot表示的是状态i中还有多少个位置没问
解释下(frac{Num[i||1<<(j-1)}{Num[i]})的意思
设(j = i | (1 << (j - 1))
num[j] 一定不大于 num[i]
因为是j向i转移不好考虑
换成i向j转移思考,i有num[j]种选择可以变成j的样子
但是有(num[i]-num[j])的选择是可以直接分辨出答案来的
所以由j向i转移的时候就只需要考虑到那num[j]种情况,所以只有(num[j]/num[i])的概率可以继续转移
余下的((num[i]-num[j])/num[j])就是已经确定的那些
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
# define int long long
const int M = 55 ;
const int N = (1 << 20) + 5 ;
using namespace std ;
int m , n ;
char s[M][M] ;
int unf[N] , Num[N] ;
double f[N] ;
# undef int
int main() {
# define int long long
scanf("%lld",&m) ;
for(int i = 1 ; i <= m ; i ++) scanf("%s",s[i] + 1) ;
n = strlen(s[1] + 1) ;
for(int i = 1 ; i <= m ; i ++)
for(int j = i + 1 , sit ; j <= m ; j ++) {
sit = 0 ;
for(int k = 1 ; k <= n ; k ++)
if(s[i][k] == s[j][k])
sit |= (1LL << (k - 1)) ;
unf[sit] |= (1LL << (i - 1)) ;
unf[sit] |= (1LL << (j - 1)) ;
}
for(int i = (1 << n) - 1 ; i >= 1 ; i --)
for(int j = 1 ; j <= n ; j ++)
if(i & (1 << (j - 1)))
unf[i ^ (1 << (j - 1))] |= unf[i] ;
for(int i = 0 ; i < (1 << n) ; i ++)
for(int j = 1 ; j <= m ; j ++)
if(unf[i] & (1LL << (j - 1)))
Num[i] ++ ;
for(int i = (1 << n) - 2 , tot ; i >= 0 ; i --) {
if(!Num[i]) continue ;
tot = n ;
for(int j = 1 ; j <= n ; j ++)
if(i & (1 << (j - 1))) --tot ;
for(int j = 1 ; j <= n ; j ++) {
if(i & (1 << (j - 1))) continue ;
f[i] += f[i | (1 << (j - 1))] / (double)tot * ((double)Num[i | (1 << (j - 1))] / (double)Num[i]) ;
}
f[i] += 1.0 ;
}
printf("%.10lf
",f[0]) ;
return 0 ;
}