题目描述

难度分:$1400$

输入$T(\leq 10^4)$表示$T$组数据。所有数据的$n$之和$\leq 2 \times 10^5$。

每组数据输入$n(2 \leq n \leq 2 \times 10^5)$和长为$n$的数组$a(0 \leq a[i] \leq 10^9)$。

把数组$a$重新排列为数组$b$，使得对于所有$1 \leq i \leq n-1$，满足：

• $b$的长为$i$的前缀的AND，等于$b$的长为$n-i$的后缀的AND（按位与）。

输出有多少个【元素下标不同】的$b$，模$10^9+7$。

例如$a=[1,1,1]$有$6$个【元素下标不同】的排列，虽然这些排列都是$[1,1,1]$。

输入样例

4
3
1 1 1
5
1 2 3 4 5
5
0 2 0 3 0
4
1 3 5 1

输出样例

6
0
36
4

算法

打表+组合数学

硬想想了一会儿没想出来，把样例打了个表，在有解的情况下发现$0$和$1$都放在了$b$数组的两端。然后开始有思路，由于按位与是个单调不增的操作，要想所有$i \in [1,n-1]$都满足前后缀的按位与结果相等，肯定就要快速达到这个最小值，不然这个条件太强了，很容易被破坏掉。

因此，我们把$a$中所有元素的按位与结果$l$放在$b$数组的两端，如果$res$在$a$中的频数不足$2$，肯定就无解了。假设$a$中有$x$个$l$，从$x$中选$2$个$l$放在两端的方案数就是$2C_{x}^{2}$，多乘个$2$是因为首尾也可以交换。剩下的$n-2$个元素在中间全排列就可以了，方案数为$A_{n-2}^{n-2}$，因此最终答案为$2C_{x}^{2}A_{n-2}^{n-2}$，组合数和排列数在$n \leq 2 \times 10^5$这个数据量下需要用到快速幂和逆元。

复杂度分析

时间复杂度

预处理$i!$（$i \in [1,n]$）的时间复杂度为$O(n)$。预处理出其对应的逆元由于需要做快速幂，因此时间复杂度为$O(nlog_2A)$，本题中$A=10^9+7$，其实就是模数。计算整个数组的与，并且统计出这个结果的频数时间复杂度都是$O(n)$，在做预处理的情况下，最后根据公式计算方案数是$O(1)$的。

而预处理只做一次，均摊下来可以把那个$log$忽略掉，算法整体的时间复杂度为$O(n)$。

空间复杂度

预处理出$i!$及其逆元需要用$O(n)$的数组把结果存储下来，这也是整个算法的额外空间复杂度。

C++ 代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 200010, MOD = 1e9 + 7;
int t, n, a[N], fact[N], infact[N];

LL fast_power(LL a, LL b) {
    LL res = 1;
    while(b) {
        if(b&1) res = res*a%MOD;
        a = a*a%MOD;
        b >>= 1;
    }
    return res;
}

LL inv(LL x) {
    return fast_power(x, MOD - 2);
}

void init() {
    fact[0] = infact[0] = 1;
    for(int i = 1; i < N; i++) {
        fact[i] = (LL)fact[i - 1]*i%MOD;
        infact[i] = inv(fact[i]);
    }
}

int C(int x, int y) {
    return (LL)fact[x]*infact[x - y]%MOD*infact[y]%MOD;
}

int A(int x) {
    return fact[x];
}

int main() {
    scanf("%d", &t);
    if(fact[0] == 0) init();
    while(t--) {
        scanf("%d", &n);
        int left;
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            if(i == 1) {
                left = a[i];
            }else {
                left &= a[i];
            }
        }
        int cnt = 0;
        for(int i = 1; i <= n; i++) {
            cnt += a[i] == left? 1: 0;
        }
        if(cnt < 2) {
            puts("0");
            continue;
        }
        printf("%d\n", 2LL * C(cnt, 2) % MOD * A(n - 2) % MOD);
    }
    return 0;
}