Codeforces Round 275 E.Game With Strings

Wings 收录于类别 ACM

2021-02-04 2021-02-04 约 1022 字预计阅读 3 分钟次阅读条评论

$n$ 个长为 $m$ 的不同字符串, 等概率地藏起来一个字符串, 然后游戏者来猜藏起来的串是什么. 每一步游戏者等概率地询问该字符串的某个位置的字符是什么. 不断地知道该字符串的一些位置的字符后, 游戏者就可以确定藏起来的串是什么, 题目要求游戏者的期望步数.

$1 \le n \le 50, 1 \le m \le 20$

这个步数期望的贡献转化没见过, 记下来.

由于期望的线性性质, 我们可以先求猜出某一个的期望步数. 这样乘以 $\frac{1}{n}$ 就是所有的期望步数了.

然后考虑如何求猜出一个串的期望步数.这里转化一下贡献, 把步数拆开, 即变为 $$E’ = \sum_{s \in ALL, |s| = 1}P(s) \cdot 1(\text{走第一步}) + \sum_{s \in ALL, |s| = 2}P(s) \cdot 1(\text{走第二步}) + \dots$$

其中$ALL$是询问集合全集, 即每个位置都询问.

可以发现, 某个字符串对答案有贡献, 当且仅当走第 $k$ 步不能确认.

再根据线性性质, 把询问$s$不能确认的字符串个数加进去, 就有 $$E = \sum_{k=0}^{m} \sum_{s \in ALL, |s| = k}P(s) \cdot \frac{\text{#不能确定的字符串}}{n}$$

(这里故意用集合元素个数把他拆开来了, 对于上面的$E’$的做法, 两个$\Sigma$其实就是在枚举所有子集)

假设某一次询问的位置集合是 $s$, 无论我用什么顺序走, 只要最后走出来的集合是 $s$, 不能确定的字符串个数是一样的, 顺序无关紧要, 于是有 $$P(s) = \frac{1}{\binom{m}{|s|}}$$ 不能确定的字符串很容易理解, 就是当前询问集合位置都相同的字符串个数.

所以我们需要枚举询问集合, 求出这个询问集合中每个位置都相同的字符串个数.

很显然状压dp.

只不过dp值不是个数, 而是不能确认的字符串集合.

个数的话无法转移, 所以要用一个能够转移的dp值 —— 集合, 然后通过集合求个数即可.

先通过枚举字符串对, 把两个字符串相等的位置拿出来, 把这两个字符串加入到dp值集合中.

得到的这些$dp(s)$值集合的所有元素直接丢到$s$的子集即可, 因为$s$的子集也一定不能确定$dp(s)$.

复杂度$O(n^2 m + 2^m m)$

cf交LD挂了

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44


const int MAXN = 55;
const int MAXM = (1<<20) + 1;

LL dp[MAXM], C[MAXN][MAXN];
int n, m;
char a[MAXN][MAXN];
double ans = 0;

int count(LL x) {
	int res = 0;
	while (x)
		x &= (x-1), res++;
	return res;
}

void init() {
	for(int i = 0; i <= m; i++)
       for(int j = C[i][0] = 1; j <= i; j++)
           C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
}

int main() {
	scanf("%d", &n);
	for (int i = 0; i < n; i++)
		scanf("%s", a[i]);
	m = strlen(a[0]);
	init();
	for (LL i = 0; i < n; i++)
		for (LL j = 0; j < i; j++) {
			int same_bit = 0;
			for (int k = 0; k < m; k++)
				if (a[i][k] == a[j][k])
					same_bit |= 1 << k;
			dp[same_bit] |= (1ll << i) | (1ll << j);
		}
	for (int s = (1 << m) - 1; ~s; s--)
		for (int i = 0; i < m; i++)
			if ((1 << i) & s)
				dp[s ^ (1 << i)] |= dp[s];
	for (int s = 0; s < (1<<m); s++)
		ans += (double)count(dp[s]) / n / C[m][count(s)];
	printf("%.10lf\n", ans);
	return 0;
}