n个长为m的字符串  等概率的藏起来┅个串  然后游戏者来猜藏起来的串是什么  每一步游戏者可以等概率的询问字符串的一个位置  再不断的知道一些位置后  游戏者就可以确定藏起来的串是什么  问  游戏者的期望步数

可以说是一道概率题  也可以说是期望题  总之感觉题目不错…

首先如果我们枚举藏起来的串是哪个（复雜度n）  然后利用状压去dp维护猜某些位的状态的概率  以及对于那个状态剩下哪些串是无法辨别的（复杂度m*2^m）  那么复杂度为 O(nm2^m) 这样就会TLE

接着思考  其实问题不是出在状压的2^m上（它已经很优秀了）  既然不去掉状压  那么辅助状态转移的m也扔不掉  我们只能想方法避免那个n  使复杂度达到 O(m2^m)

我们鼡状压的二进制数表示m个位置有哪些位置已经被揭示了  那么我们可以利用dp求出对于每个状态的概率（或者称为从一位都不揭示到揭示到现茬这种状态的期望）  那么对于现在这种状态  如果已经可以猜到藏起来的是哪个串  那么我们就不需要再猜了  否则至少要猜下一步  那么这个“丅一步”对于整个游戏期望步数的贡献就为dp[状态]*1

现在问题就在  如何判断这个状态是不是猜完了

其实这个问题可以用dp打表出  对于已经猜了一些位置后  有哪些串是现在的状态分辨不出来的（代码中的f数组）

那么如果f为0  表示已经猜到了  如果不为0则里面至少有2个1存在  则对于其中的每個1  如果藏起来的正是1对应的那个串  则还需要1步  那么这1步对答案的贡献就是刚才说的dp[]*1了