Divide by Zero 2021 and Codeforces Round #714 (Div. 2) B. AND Sequences思维，位运算 难度1400

题目链接： Problem - B - Codeforces

题目

Example

input

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

output

6
0
36
4

题意

给一串数，用这n个数排几种序列，使得 i=1~(n-1)

输出有几种序列满足情况

题解

附  ： & -- 位运算之一，有0则0

不用怀疑，一堆数&完后，得到的数<=这堆数的任意一个数

因为每一位只要有一个数==0，这一位就=0，否则为1

 

记最后&完所有数的数为num, 如果这串数中有>=2个等于num的数,那么

把这两个数放在最后和最前面,其他的数,全排就好了

记有cnt个数==num,结果为

代码

#include <iostream>

using namespace std;

typedef long long ll;
const int N = 2e5+10, mod = 1e9+ 7;;
int a[N];

int main()
{
    int t;
    cin >> t;
    while(t --)
    {
        int n;
        cin >> n;
        for(int i = 1; i <= n ; i ++)    cin >> a[i];
        
        int num = a[1];
        
        for(int i = 2; i <= n; i ++)
            num &= a[i];
        
        int cnt = 0;
        for(int i = 1; i <= n; i ++)
            if(num == a[i])
                cnt ++;
                
        if(cnt < 2)
            cout << 0 << endl;
        else
        {
            cnt = (ll)cnt * (cnt-1)% mod;
            for(int i = 2; i <= n-2; i ++)    
                cnt = (ll)cnt * i % mod;
            
            cout << cnt << endl;
        }
    }
    return 0;
}