题解：CF1773G Game of Questions

模拟赛中的题是求排列数，不过改为求排列数是纯诈骗，需要从求概率的角度来看这题。

先来考虑 O(3^m) 的做法：

• 这一部分去看其他题解可能更好
• 首先注意到一个题目第二次考不会影响当前集合。
• 统计可以将 S 改变为 T 的题目数量 c。（满足 T \ne S 且 T \ne \varnothing）
• 然后依次转移，转移到 T 的概率就是 dp_S 乘可以转移到 T 的题目数，再除以 c。
• 这样正推求概率 dp 是没有问题的，而且 T \ne S 且 T \ne \varnothing 所以是有单调性的，且所有都会到达最终状态。
• 因为要枚举子集，所以复杂度 O(3^m)。

考虑 O(m^2 2^m) 的做法。

• 改写一下转移，设 g_T 表示 T 在 n 个集合中的出现次数少。
• 发现实际上 0 < |S \cap T| 这个限制实际是不需要的，因为 dp_0 并不会对答案产生任何贡献。
  • 所以实际转移是：\frac{dp_S}{c_S} \times g_T \to dp_{S \cap T} (|S \cap T| < |S|)。
• 求 c_S。
  • 首先一个普通容斥，变为求包含 S 的 T，和完全不包含 S 的 T。
  • 普通高维前缀和。
• 由于 |S \cap T| < |S| 这个限制，我们考虑枚举 popcount 从 m 到 0，由 popcount > i 的状态转移到 popcount = i 的状态。这样那个限制就没有了。
• 优化转移。
  • 考虑一个普通容斥，dp_S 可以先加上每对 S \in S',T 的贡献，然后减去那些 S' \cap T \ne S 且 S \in S' \cap T 的总和。
  • 第一步可以高维前缀和，第二步需要高维差分。

Code:

#include <bits/stdc++.h>

using namespace std;
using LL = long long;

const int MAXM = (1ll << 20) + 3;

int n, m, pc[MAXM];
double c[MAXM], c1[MAXM], c2[MAXM]; // c 数组
double g[MAXM]; // g 数组
double f[MAXM], tmp[MAXM], _f[MAXM]; 

void ADD(double &x, double w){ x += w; }

void hdi_suf(double *A){
    for(int i = 0; i < m; i++){
        for(int s = 0; s < (1ll << m); s++) if((s >> i) & 1) ADD(A[s ^ (1ll << i)], A[s]);
    }
}
void _hdi_suf(double *A){ // 高维后缀差分
    for(int i = 0; i < m; i++){
        for(int s = 0; s < (1ll << m); s++) if((s >> i) & 1) ADD(A[s ^ (1ll << i)], - A[s]);
    }
}
void hdi_pre(double *A){
    for(int i = 0; i < m; i++){
        for(int s = 0; s < (1ll << m); s++) if((s >> i) % 2 == 0) ADD(A[s ^ (1ll << i)], A[s]);
    }
}

int main(){
  ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> m;
    int R = (1ll << m) - 1;
    for(int s = 0; s < (1ll << m); s++){
        for(int i = 0; i < m; i++) pc[s] += (s >> i) & 1;
    }
    for(int i = 1; i <= n; i++){
        int S = 0;
        for(int j = 0; j < m; j++){
            char ch; cin >> ch, S += (ch == '1') * (1ll << j);
        }
        g[S]++, c1[S]++, c2[S]++;
    }
    hdi_pre(c1), hdi_suf(c2);

  for(int s = 0; s < (1ll << m); s++){
        c[s] = (s == 0 ? 0 : n - c1[s ^ R] - c2[s]);
        if(c[s] < 0) return 1;
    }

    f[R] = 1;
    hdi_suf(g); // 先对 g 做一遍后缀和
    for(int i = m - 1; i >= 1; i--){
        for(int s = 0; s < (1ll << m); s++) tmp[s] = f[s], f[s] = (c[s] == 0 ? 0 : f[s] / c[s]);
        hdi_suf(f);
        for(int s = 0; s < (1ll << m); s++) _f[s] = f[s] * g[s];
        _hdi_suf(_f);

        for(int s = 0; s < (1ll << m); s++){
            if(pc[s] > i) f[s] = tmp[s];
            if(pc[s] == i) f[s] = _f[s];
            if(pc[s] < i) f[s] = 0;
        }
    }
    vector<double> ans(m, 0);
    for(int s = 1; s < (1ll << m); s++){
      if(c[s] != 0) continue; // 只统计最终状态的概率 
        for(int i = 0; i < m; i++) if((s >> i) & 1) ADD(ans[i], f[s]);
    }
  cout << fixed << setprecision(10) << ans[0] << "\n";
    return 0;
}