AGC020F

有趣的无限转有限（double 转 int），似乎扩展了状态压缩的定义。

题意：给定一个长度为 $C$ 的圆周和 $n$ 个长度为 $l_i$ 的圆弧，随机将圆弧放在圆周的任意位置（不一定是整数），求圆周上的每一个点都被覆盖的概率。$n\leq 6, C\leq 50$，$C, l_i$ 均为整数。

数据范围这么小，几乎能想出怎么求就可以了。

首先固定一个位置，比如固定最大 $l_i$ 开始的位置为 0。这样其他的位置就比较好描述了。

首先，题目中有一个关键信息：$C, l_i$ 均为整数，虽然放的位置可能不是。如果我们将小数部分拆开看的话，其实他们到底是多少我们是无法枚举的，但是我们并不需要他们的准确值，也就是说，我们只需要他们的相对关系。这样，我们将 $n - 1$ 个 $[0, 1)$ 的小数映射到了 $[1, n - 1]$，这个离散化的过程就是第一次状态压缩。

容易发现两个小数相同的概率是 0，所以我们可以使用一个排列的方式表示这 $n - 1$ 个小数的大小关系。然后考虑在确定小数状态下，如何计算完全覆盖。

$n$ 如此之小，直接考虑状态压缩，记录 $f(s, len)$ 表示已经放入了 $s$ 状态的圆弧，最远达到了 $len$ 位置。注意 $len$ 包含了小数部分，为了方便，我们将整数部分 $\times n$，这样 $\bmod n$ 的就是小数部分。

枚举下一个数放在了哪个位置，直接考虑转移，这里不再详细展开，时间复杂度 $O((n - 1)! 2^{n - 1} (nC) ^ 2)$，可以通过。

注意实现的时候有两个坑点：

1. 代码中我直接对 $l_i$ 枚举全排列，注意可能出现 $l_i$ 相同的情况，这样 std::next_permutation 的次数不会达到 $(n - 1)!$，需要记录有多少。
2. 代码中转移的时候必须先枚举下一个数放在了哪个位置（枚举了位置自然知道是哪个圆弧），顺序转移，否则会出现由于下一个数枚举的混乱导致算重情况。

给出参考代码。

double solve()
{
	memset(f, 0, sizeof(f));
	int m = n - 1;
	f[0][a[0] * n] = 1;
	for (int nxt = 0; nxt <= C * n; ++ nxt)
		for (int ls = nxt; ls <= C * n; ++ ls)
			for (int s = 0; s < (1 << m); ++ s)
				if (nxt % n && !(s >> (nxt % n - 1) & 1))
					f[s | (1 << (nxt % n - 1))][std::min(n * C, std::max(ls, nxt + a[nxt % n] * n))]
						+= f[s][ls];
	// for (int i = 0; i < n; ++ i) printf("%d ", a[i]);
	// printf(": %.10lf\n", f[(1 << m) - 1][n * C]);
	return f[(1 << m) - 1][n * C];
}

int main()
{
	std::cin >> n >> C;
	for (int i = 0; i < n; ++ i) std::cin >> a[i];
	std::swap(*std::max_element(a, a + n), a[0]);
	std::sort(a + 1, a + n);
	double res = 0;
	int cnt = 0;
	do res += solve(), cnt ++; while (std::next_permutation(a + 1, a + n));
	for (int i = 1; i < n; ++ i) res /= C;
	printf("%.14lf\n", res / cnt);
	return 0;
}