题目描述
难度分:$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;
}