首先可以注意到关键结论：
一个题操作多次，则最多只有第一次操作会对答案产生影响。
因此可以想到不把题目这个维度记到 dp 状态中，容易通过快速枚举子集得到 \(O(m3^m)\) 的解法，精细实现可以做到 \(O(3^m)\)。
考虑对该做法进行优化。记录 \(c_i\) 表示若当前还剩下 \(i\) 集合的参赛者，则还有多少道题可以使得做完该题之后参赛者集合发生变化。此时只有两种情况不合法：
-
所有人都会做这个题。
-
所有人都不会做这个题。
正难则反即可得到 \(c_i=n-\sum\limits_{j\subseteq\bar i}g_j-\sum\limits_{j\supseteq i}g_j\)，可以两次 FMT 在 \(O(m2^m)\) 的时间复杂度内求解答案。
同样考虑 dp。设 \(f_i\) 表示问完所有题之后剩余 \(i\) 集合内的人的概率。暴力的转移形如枚举选取的题目集合 \(j\) 然后转移到题目集合为 \(i\cap j\) 的情况。记 \(cnt_i\) 表示通过集合为 \(i\) 的题目的数量，那么显然有转移方程：
注意到转移的形式很特殊（\(i\cap j\) 一定是 \(j\) 的真子集）保证转移方程没有后效性只需要保证从大集合转移到小集合即可，容易想到按照集合的 popcount 从大到小转移。
前面已经分析过 \(j\) 这个题型无效当且仅当 \(i\cap j\) 为空或 \(i\subseteq j\)。此时注意到 \(f_0\) 不会转移到任何集合也就是不会继续影响答案，而最终算答案显然也不需要考虑 \(f_0\)。因此考虑直接去掉 \(i\cap j\) 为空的条件。
然后注意到按照集合的 popcount 从大到小转移可以直接避免出现 \(i\subseteq j\) 的情况，因此此时直接做上面的转移就是对的。
换个形式写上面的转移方程，其实就是：
发现这就是个子集与卷积的形式，使用 FMT 即可简单解决。
因为要枚举 \(O(m)\) 个不同的 popcount 值，每次枚举都需要做 \(O(1)\) 次整体的 FMT，因此总时间复杂度为 \(O(m^22^m)\)，简单卡常后可以通过该题。
namespace Loyalty
{inline void init() { }int n, m;int mcnt[1 << 20], m1[1 << 20], m2[1 << 20];ld g[1 << 20], f[1 << 20], la_f[1 << 20], nw_f[1 << 20];inline void main([[maybe_unused]] int _ca, [[maybe_unused]] int atc){cin >> n >> m;for (int i = 1; i <= n; ++i){int state = 0;for (int j = 0; j < m; ++j){char o;cin >> o;if (o == '1')state |= (1 << j);}++m1[state], ++m2[state], ++g[state];}for (int i = 0; i < m; ++i)for (int j = 0; j < (1 << m); ++j)if (~j >> i & 1)m1[j ^ (1 << i)] += m1[j];elsem2[j ^ (1 << i)] += m2[j];for (int i = 1; i < (1 << m); ++i)mcnt[i] = n - m1[i ^ ((1 << m) - 1)] - m2[i];f[(1 << m) - 1] = 1;for (int i = 0; i < m; ++i)for (int j = 0; j < (1 << m); ++j)if (j >> i & 1)g[j ^ (1 << i)] += g[j];for (int i = m - 1; i; --i){for (int j = 0; j < (1 << m); ++j)la_f[j] = f[j], f[j] = (!mcnt[j] ? 0 : f[j] / mcnt[j]);for (int i = 0; i < m; ++i)for (int j = 0; j < (1 << m); ++j)if (j >> i & 1)f[j ^ (1 << i)] += f[j];for (int j = 0; j < (1 << m); ++j)nw_f[j] = f[j] * g[j];for (int i = 0; i < m; ++i)for (int j = 0; j < (1 << m); ++j)if (j >> i & 1)nw_f[j ^ (1 << i)] -= nw_f[j];for (int j = 0; j < (1 << m); ++j){int len = __builtin_popcount(j);if (len > i)f[j] = la_f[j];else if (len == i)f[j] = nw_f[j];elsef[j] = 0;}}ld res = 0;for (int i = 1; i < (1 << m); i += 2)if (!mcnt[i])res += f[i];cout << res << '\n';}
}