「CF2233E2」Permutation Transmission (Difficult Version)

    「CF2233E2」Permutation Transmission (Difficult Version)

    CF2233E2

    对于一个长度为 nn 的排列 pp,记 k=⌈log⁡2(n+1)⌉k = \lceil \log_2(n + 1) \rceil。

    系统原本会生成 kk 个长度为 nn 的 0101 串,对于第 jj (0≤j<k0 \leq j < k) 个二进制位,0101 串的第 ii 个字符表示 pip_i 的第 jj 个二进制位的值。

    现在,这 kk 个 0101 串被打乱,因此不知道每个 0101 串对应哪个二进制位。

    给定打乱后的 kk 个 0101 串,求有多少个不同的关于 nn 的排列 pp,使得至少存在一种 0101 串与二进制位的对应关系,能够还原出 pp。

    数据范围:1≤n≤2×1051 \leq n \leq 2\times 10^5。

    时空限制:22s / 512512MiB。

    Solution

    首先可以做一些简单的判断:

    • 不存在某一列的串均为 00,这样就会使得 pp 中存在 00。
    • 不存在某两列的串相等,这样就会使得 pp 中存在两个相同的数。

    那么可以保证,不论串和二进制位的对应关系是怎么样,pp 一定是由 nn 个互不相同的正整数构成。

    在该种情况下,当 pp 是关于 nn 的排列的时候,∑p\sum p 一定是最小的。反过来也成立。

    所以我们现在需要找到一种串和二进制位的对应关系,使得 ∑p\sum p 最小。假设第 ii 个 0101 串一共有 cic_i 个 11,那么将其对应到第 jj 个二进制位产生的贡献为 ci×2jc_i \times 2^j。

    所以要想使得 ∑p\sum p 最小,只需将所有 0101 串按照 11 的个数降序排序即可。降序排序后,先检查一下还原的排列是否为关于 nn 的排列。

    此时还要统计方案数,不难发现 11 的个数相同的两个串可以交换位置,所以设 cnti\mathrm{cnt}_i 表示有多少个 0101 串 11 的个数等于 ii,答案即为 ∏i=1ncnti!\prod_{i = 1}^n \mathrm{cnt}_i !。

    #include <bits/stdc++.h>
    
    using i64 = long long;
    
    #define debug(a) std::cout << #a << '=' << (a) << ' '
    
    template <class T>
    inline void chmin(T &x, const T &y) {
        if (x > y) {
            x = y;
        }
    }
    template <class T>
    inline void chmax(T &x, const T &y) {
        if (x < y) {
            x = y;
        }
    }
    
    // 精确取对数(上取整):找到最小整数 t,使得 a^t >= b
    int iLog(i64 a, i64 b) {
        int t = 0;
        i64 v = 1;
        while (v < b) {
            t ++; if (v > b / a) break;
            v *= a;
        }
        return t;
    }
    
    const int N = 200100;
    
    int n, k;
    std::string str[20];
    int one[20];
    int ord[20];
    
    int p[N];
    
    int buc[N];
    i64 fact[20];
    
    void work() {
        std::cin >> n, k = iLog(2, n + 1);
    
        for (int j = 0; j < k; j ++) {
            std::cin >> str[j];
            str[j] = " " + str[j];
    
            one[j] = 0;
            for (int i = 1; i <= n; i ++) {
                one[j] += str[j][i] == '1';
            }
        }
    
        for (int j = 0; j < k; j ++) {
            ord[j] = j;
        }
        std::sort(ord, ord + k, [&] (int x, int y) -> bool {
            return one[x] > one[y];
        });
    
        for (int i = 1; i <= n; i ++) {
            p[i] = 0;
        }
        for (int j = 0; j < k; j ++) {
            for (int i = 1; i <= n; i ++) {
                if (str[ord[j]][i] == '1') {
                    p[i] += (1 << j);
                }
            }
        }
        
        std::sort(p + 1, p + 1 + n);
        for (int i = 1; i <= n; i ++) {
            if (p[i] != i) {
                std::cout << 0 << '\n';
                return;
            }
        }
    
        fact[0] = 1;
        for (int i = 1; i <= k; i ++) {
            fact[i] = fact[i - 1] * i;
        }
    
        for (int i = 1; i <= n; i ++) {
            buc[i] = 0;
        }
        for (int j = 0; j < k; j ++) {
            buc[one[j]] ++;
        }
        
        i64 ans = 1;
        for (int i = 1; i <= n; i ++) {
            ans *= fact[buc[i]];
        }
        std::cout << ans << '\n';
    }
    
    int main() {
        std::ios::sync_with_stdio(0);
        std::cin.tie(0);
    
        int T;
        std::cin >> T;
    
        while (T --) {
            work();
        }
    
        return 0;
    }