CF1214F 题解

Corzica · 2024-11-14 15:39:06 · 题解

这里提供一个 O(m^22^m) 的做法。

我们可以把这个问题转化成一个子集 dp 的问题。对于一个状态而言，我们可以得到对他仍有贡献的问题个数，那么想要让一个转移发生，当且仅当这个问题排在第一位，系数为 \frac{\text{这个问题的个数}}{\text{有意义的问题总个数}}，朴素实现复杂度为 O(3^m)。

我们注意到转移的方式实际上和 and 卷积非常的相似。我们把状态作为下标，它的出现次数作为值。当前 dp 数组的每一个状态的位置都除以对它而言有意义的问题总个数。这两个数组做一次卷积就能够得到这一次转移后的 dp 数组。

为了使得 dp 转移有一个固定顺序，这里还要加上一维表示现在转移的这些状态的 popcnt。

总时间复杂度就是 O(m^22^m)。

代码：

#include<bits/stdc++.h>
using namespace std;
int n, m, val[2000006],  jie[100005], inv[1000005], lim, vvis[2000006], a[200005];
int sum[2000006], siz[2000006], sums[2000006];
long double f[21][2000006], g[2000006], r[2000006];
const int mod = 998244353, inv2 = 499122177;
string s;
inline int zhuan(string s) {
    int cnt = 0;
    for (int i = 0; i < s.size(); i++) {
        cnt = cnt * 2 + s[i] - '0';
    }
    return cnt;
}
inline int ksm(int p, int q = mod - 2) {
    int base = 1;
    while (q) {
        if (q & 1)base = base * 1ll * p % mod;
        q >>= 1;
        p = p * 1ll * p % mod;
    }
    return base;
}
inline int C(int p, int q) {
    return jie[p] * 1ll * inv[q] % mod * inv[p - q] % mod;
}
const int Cand[2][2] = {{1, 1}, {0, 1}}, ICand[2][2] = {{1, - 1}, {0, 1}};
inline void fwt(long double *f, const int c[2][2], int n) {
    int op;
    for (int len = 1; len < n; len <<= 1) {
        for (int p = 0; p < n; p += ( len << 1)) {
            for (int i = p; i < p + len; i++) {
                op = f[i];
                f[i] = (c[0][0] * 1ll * f[i] + c[0][1] * 1ll * f[i + len]) ;
                f[i + len] = (c[1][0] * 1ll * op + c[1][1] * 1ll * f[i + len]) ;
            }
        }
    }
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    jie[0] = 1;
    for (int i = 1; i <= 100000; i++) {
        jie[i] = jie[i - 1] * 1ll * i % mod;
    }
    for (int i = 100000; i >= 0; i--) {
        inv[i] = ksm(i);
    }
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> s;
        a[i] = zhuan(s);
        val[zhuan(s)]++;
        sum[zhuan(s)]++;
        sums[zhuan(s)]++;
    }
    lim = (1 << m) - 1;
    for (int i = 0; i <= lim; i++) {
        siz[i] = siz[i >> 1] + (i & 1);
        g[i] += val[i];
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j <= lim; j++) {
            if (((j >> i) & 1)) {
                sum[j] += sum[j ^ (1 << i)];
            }
        }
        for (int j = lim; j >= 0; j--) {
            if (!((j >> i) & 1)) {
                sums[j] += sums[j ^ (1 << i)];
            }
        }
    }
    f[m][lim] = 1;
    fwt(g, Cand, lim);
    long double ans = 0;
    for (int i = m; i >= 1; i--) {
        if (i != m) {
            memcpy(f[i], r, sizeof(r));
            fwt(f[i], ICand, lim);
        }
        for (int j = 0; j <= lim; j++) {
            if (siz[j] != i) f[i][j] = 0;
            else {
                if ( ( n - sums[j] - sum[lim ^ j]) == 0) {
                    if ((j >> (m - 1)) & 1 ) {
                        ans += f[i][j];
                    }
                    f[i][j] = 0;
                } else f[i][j] = f[i][j] / ( n - sums[j] - sum[lim ^ j]);
            }
        }
        fwt(f[i], Cand, lim);
        for (int j = lim; j >= 1; j--) {
            r[j] = (r[j] + f[i][j]  * g[j]) ;
        }
    }
    cout << fixed << setprecision(10) << ans;
}