Divide by Zero 2021 and Codeforces Round #714 (Div. 2)

B题 AND Sequences

原题链接

题意

给定一个序列, 问这个序列的所有全排列中, 有多少满足对任意的\(1 < i < n\):
\(a_{1} \& a_{2} \& ... \& a_{i} = a_{i + 1} \& a_{i + 2} \& ... \& a_{n}\)

思路

对于一个\(a\)序列:
设\(k = a_{1} \& a_{2} \& ... \& a_{n}\)
对任意一个排列方式, 当\(a_{1} = a_{n}\)时:
\(a_{1} \& a_{2} \& ... \& a_{n - 1} = a_{2} \& a_{3} \& ... \& a_{n}\)
而当\(a_{1} = a_{n} = k\)时:
就有:\(k \& a_{2} \& ... \& a_{n - 1} = a_{2} \& a_{3} \& ... \& k\)
对任意的\(i\)均成立.
那么我们只需找到等于\(k\)的\(a_{i}\)的个数\(cnt\), 任选两个放在首尾\(A^{2}_{cnt}\), 其余数字放中间\(A^{cnt - 2}_{cnt - 2}\)

代码

#include 
#include 

using namespace std;

const int N = 2e5 + 10;
const int p = 1e9 + 7;
typedef long long LL;

int a[N];

LL calc(LL a)
{
    LL ans = 1;
    for (int i = 1; i <= a; i ++ )
        ans = ans * i % p;
    return ans;
}

void solve()
{
    LL n;
    cin >> n;
    for (int i = 1; i <= n; i ++ )
        cin >> a[i];
    int k = (1 << 31) - 1;
    for (int i = 1; i <= n; i ++ )
        k = k & a[i];
    long long cnt = 0;
    for (int i = 1; i <= n; i ++ )
        if (a[i] == k)
            cnt++;
    if (cnt < 2){
        puts("0");
        return;
    }
    cout << (cnt - 1) * cnt % p * calc(n - 2) % p << endl;
    return;
}

int main()
{
    int t;
    cin >> t;
    while (t -- )
        solve();
    return 0;
}