这题增进了我对概率论的一些理解。

设当前局面为 。

容易发现，在一次 的过程中，大部分的题目都不会对 产生影响。

我们称对 序列产生影响的题目是 "关键的"，显然，夹在两个“关键”题目之间的非关键题目可以任意排列，它们不会对概率产生影响。（这是比较重要的一点）。

那我们的任务主要就是，在确定 序列的过程中，顺便确定 "关键题目的排列"。

只会越变越小，这给了我们 DP 的状态和方式：设 表示到达局面 的概率，转移则枚举子集。

枚举从 转到 是因为哪道题目，设为 ，那么有 。设能够改变 的题目有 个（即满足 的 的个数），那么这 个题目显然不会在 以前的地方出现（否则当前局面就不是 了）。在这一类题目中，我们要求当前枚举的 最早出现，对应的概率就是 ，那么就会有 。

这显然过不去，但是注意到后继局面（即 ） 相同的转移可以合并，故设 表示满足 的 的个数，那么 ，上述转移就改写为 。

可以递推预处理，具体地，取任意不属于 的元素 ，有 。

上述工作都可以在 时间内完成，故总时间复杂度为 ，可以通过。

#include <bits/stdc++.h>
using namespace std;
const int N = 2e5 + 5,M = 1 << 17;
typedef double db;
vector<int> g[M];
db f[M],ans;
int n,m;
int cnt[M];
int pop[M];
int cc[M];
#define lowbit(x) ((x)&(-(x)))
int tid[M];
int main()
{
	cin >> n >> m;
	for(int i = 1;i <= n;i++)
	{
		string st;int S = 0;
		cin >> st;
		for(int j = 0;j < m;j++)
			if(st[j] == '1') S |= (1 << j);
		++cnt[S];
	}
	for(int i = 1;i < (1 << m);i++) pop[i] = pop[i >> 1] + (i & 1);
	for(int S = (1 << m) - 1;S >= 0;--S)
	{
		g[S].resize(1 << pop[S]);
		if(S + 1 == (1 << m))
		{
			for(int T = S & (S - 1),i = 0;T;T = (T - 1) & S,++i)
				g[S][i] = cnt[T],cc[S] += cnt[T];
			continue;
		}
		int from = S | lowbit(((1 << m) - 1) ^ S),p = lowbit(((1 << m) - 1) ^ S);
		for(int T = from & (from - 1),i = 0;T;T = (T - 1) & from,++i)
			tid[T] = i;
		for(int T = S & (S - 1),i = 0;T;T = (T - 1) & S,++i)
			g[S][i] = g[from][tid[T]] + g[from][tid[T | p]],cc[S] += g[S][i];
	}
	f[(1 << m) - 1] = 1;
	for(int S = (1 << m) - 1;S;--S)
	{
		if(cc[S] == 0)
		{
			if(S & 1) ans += f[S];
			continue;
		}
		for(int T = S & (S - 1),i = 0;T;T = (T - 1) & S,++i)
			f[T] += f[S] * g[S][i] / cc[S];
	}
	printf("%.9lf\n",ans);
	return 0;
}