「CF2233E2」Permutation Transmission (Difficult Version)

发表于 分类于 本文字数： 885 阅读时长 ≈ 1 分钟

Description

Link：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 !。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
#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;
}