期望概率 codeforces 482C

题面

题意:

给定n个长度为m的字符串,你每次都有等同概率去猜一个没有猜过的字符以及位置,
如果可以通过猜的信息推断出n个字符串,那么就算满足条件,求期望

题解:

我们有一个初步的想法,通过枚举每一个串,我们假设是最后的串

那么我们只需要枚举所有集合,表示你已经猜了哪些数了,并且枚举下一次猜的位置,计算这个位置可以排除多少的字符串

复杂度为O(n^{2}m2^{m})

显然是会t掉的

那么如何优化这个复杂度呢

我们可以发现 2^{m} 是无法优化的

我们只需要这样做,设f[i] 表示选的集合为i的时候,对于n个串所造成排除的贡献

我们可以通过O(n^{2}m+2^{m}m)

具体做法就是枚举所有的字符串的相同的字符集合,也就是不能排除的集合,设其为s,我们正在枚举第j个字符串

于是就把f[s]|=(1<\<j)就可以了

然后dp的话就是统计剩余集合可以选哪些位

并且把这些位的期望利用处理出来的f数组来线性相加就行了

总复杂度O(2^{m}m)

233~~