B. AND Sequences___Divide by Zero 2021 and Codeforces Round #714 (Div. 2)_you are given an array a of size n. each eleme

传送门
B. AND Sequences
time limit per test2 seconds
memory limit per test256 megabytes
inputstandard input
outputstandard output
A sequence of n non-negative integers (n≥2) a1,a2,…,an is called good if for all i from 1 to n−1 the following condition holds true:
a1&a2&…&ai=ai+1&ai+2&…&an,
where & denotes the bitwise AND operation.

You are given an array a of size n (n≥2). Find the number of permutations p of numbers ranging from 1 to n, for which the sequence ap1, ap2, … ,apn is good. Since this number can be large, output it modulo 109+7.

Input
The first line contains a single integer t (1≤t≤104), denoting the number of test cases.

The first line of each test case contains a single integer n (2≤n≤2⋅105) — the size of the array.

The second line of each test case contains n integers a1,a2,…,an (0≤ai≤109) — the elements of the array.

It is guaranteed that the sum of n over all test cases doesn’t exceed 2⋅105.

Output
Output t lines, where the i-th line contains the number of good permutations in the i-th test case modulo 109+7.

Example
inputCopy
4
3
1 1 1
5
1 2 3 4 5
5
0 2 0 3 0
4
1 3 5 1
outputCopy
6
0
36
4
Note
In the first test case, since all the numbers are equal, whatever permutation we take, the sequence is good. There are a total of 6 permutations possible with numbers from 1 to 3: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1].

In the second test case, it can be proved that no permutation exists for which the sequence is good.

In the third test case, there are a total of 36 permutations for which the sequence is good. One of them is the permutation [1,5,4,2,3] which results in the sequence s=[0,0,3,2,0]. This is a good sequence because

s1=s2&s3&s4&s5=0,
s1&s2=s3&s4&s5=0,
s1&s2&s3=s4&s5=0,
s1&s2&s3&s4=s5=0.
我的超时代码

#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<math.h>
#include<iostream>
#include<algorithm>
#include<string>
#include<sstream>
#include<vector>
#include<map>
#include<set>
#include<ctype.h>
#include<stack>
#include<queue>
#ifdef LOCAL
FILE*FP=freopen("text.in","r",stdin);
//FILE*fp=freopen("text.out","w",stdout);
#endif
using namespace std;
#define ll long long
#define mem(a,b) memset(a,b,sizeof(a))
#define _forplus(i,a,b) for( register int i=(a); i<=(b); i++)
#define _forsub(i,a,b) for( register int i=(a); i>=(b); i--)
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define INF 1000000007
const double pi=acos(-1);
#define N 200005
ll p[N];
int n;
void pre(){
	p[0]=1;
	_forplus(i,1,N-2){
		p[i]=p[i-1]*i%INF;
	}
}
int cnt0[32];
int cnt1[32];
int a[N][32];
int vis[N];
void read(int i,int x){
	int cnt=0;
	while(x){
		cnt++;
		int te=x&1;
		a[i][cnt]=te;
		if(te)cnt1[cnt]++;
		x>>=1;
	}
	_forplus(i,1,31){
		cnt0[i]=n-cnt1[i];
	}
}//读入

int main(){
	pre();//做阶乘表 
	int t;
	scanf("%d",&t);
	while(t--){
		mem(cnt0,0);
		mem(cnt1,0);
		mem(a,0);
		mem(vis,0);//没排 
		scanf("%d",&n);
		int x;
		_forplus(i,1,n){
			scanf("%d",&x);
			read(i,x);
		}
		int flag=1;
		_forplus(i,1,31){
			if(cnt0[i]==0)continue;
			if(cnt0[i]==1){
				flag=0;//没这样的序列了 
				break;
			}else{
				_forplus(j,1,n){
					if(a[j][i])vis[j]=1;
				}
			} 
		}
		if(flag==0){
			printf("0\n");
		}else{
			ll sum=0;
			_forplus(j,1,n){
				if(!vis[j])sum++;
			}
			printf("%d\n",p[n-2]*sum*(sum-1)%INF);
		}
	}
	return 0;
}
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

橙名大佬的正解

#pragma GCC optimize("O3")
//#pragma GCC target("avx")
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#include <vector>
#include <set>
#include <map>
#include <unordered_set>
#include <unordered_map>
#include <queue>
#include <ctime>
#include <cassert>
#include <complex>
#include <string>
#include <cstring>
#include <chrono>
#include <random>
#include <bitset>
#include <iomanip>
#include <list>
#ifdef LOCAL
FILE*FP=freopen("text.in","r",stdin);
//FILE*fp=freopen("text.out","w",stdout);
#endif
using namespace std;
#define re return
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define make_unique(x) sort(all(x)),x.resize(unique(all(x))-x.begin())
#define fi first
#define se second
#define ss second.second
#define sf second.first
#define ff first.first
#define fs first.second
#define sqrt(x) sqrt(abs(x))
#define mp make_pair
#define PI 3.14159265358979323846
#define E 2.71828182845904523536
#define er erase
#define in insert
#define fo(i,n) for((i)=0;(i)<(n);(i)++)
#define ro(i,n) for((i)=n-1;(i)>=0;(i)--)
#define fr(i,j,n) for((i)=(j);(i)<(n);(i)++)
#define rf(i,j,n) for((i)=((n)-1);(i)>=(j);(i)--)
typedef long double ld;
typedef long long ll;
typedef unsigned long long ull;
typedef unsigned int uint;
void eras(map<int,int> &m,int x)
{
    m[x]--;
    if (!m[x]) m.erase(x);
}
const int N=(int)2e5+100;
const int M=(int)1e7+10;
const int inf=(int)1e8;
const double eps=1e-9;
#define filename ""
    ll mod=(ll)1e9+7;
ll stup(ll x,ll m=mod-2)
{
    ll o=1;
    while(m)
    {
        if (m&1)
        {
            o=o*x%mod;
        }
        x=x*x%mod;
        m>>=1;
    }
    re o;
}
    ll fact[N],ofact[N];
    int a[N];
int main()
{
    //freopen("input.txt","r",stdin);
    //freopen("output.txt","w",stdout);
    //freopen(filename".in","r",stdin);
    //freopen(filename".out","w",stdout);
    //freopen("ans.txt","w",stdout);
    mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
    srand(time(0));
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int T,i;
    fact[0]=ofact[0]=1;
    fr(i,1,N)
    {
        fact[i]=fact[i-1]*i%mod;
        ofact[i]=stup(fact[i]);
    }
    cin>>T;
    while(T--)
    {
        int n,i;
        cin>>n;
        fo(i,n)
        {
            cin>>a[i];
        }
        int sum=a[0];
        fo(i,n)
        {
            sum&=a[i];
        }
        ll k=0;
        fo(i,n)
        {
            if (a[i]==sum)
            {
                k++;
            }
        }
        cout<<k*(k-1)%mod*fact[n-2]%mod<<'\n';
    }
}

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
114
115
116
117
118
119
120
121
122
123
124
125

惊艳的是，我弄 了随机数据，和他一比，龟速。
惊讶之情无以言表

我的规律，是一个雏形，其实应该思维活跃想想：
我：那些二进制1的个数不是n的位数应该排除掉1只留下0，放在两端，使结果总是一样
快规律：那些二进制1的个数不是n的位数应该排除掉1只留下0，应该是：
所有数的交集，这样我们只求所有数的ADD。

这，就是要告诉我们要多找规律，有想法还要再琢磨。