B. AND Sequences | #714 Div.2

LONGNEW·2021년 7월 22일
0

CP

목록 보기
56/155

https://codeforces.com/contest/1513/problem/B
시간 2초, 메모리 256MB

input :

  • t (1 ≤ t ≤ 104)
  • n (2 ≤ n ≤ 2⋅105)
  • a1, a2, …, an (0 ≤ ai ≤ 109)

output :

  • Output t lines, where the i-th line contains the number of good permutations in the i-th test case modulo 109+7.
    t줄을 출력하시오. i번째 줄에서는 good인 배열의 수를 10^9 + 7로 얻은 나머지를 출력하시오.

조건 :

  • 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 & ai + 2 & … & an,
    n개의 음수가 아닌 정수로 이루어진 배열이 good이라고 될 경우 위의 좌변과 우변이 동일해야 합니다.

  • 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
    a배열이 주어질 때 이 원소를 나열하는 방법들 중 good인 순열의 개수를 찾으시오.


AND연산이 수행될 경우

기준값

AND 연산을 수행하면서 간다면 값이 커지지는 않고 차라리 작아진다.
동일한 비트를 가지고 있는 수들이 아니라면 0이 되어버리게 되고 그렇지 않다면 가장 작은 수를 계속 가지고 있게 된다.
0이 되는 부분이 생긴다면 반대편도 그러해야한다.

최솟값

어차피 값은 최솟값을 유지하거나 동일한 비트가 없어 0이 되게 된다.
이 최솟값 비트를 모든 원소들이 다 가지고 있다면 생각을 더 해야 한다.
동일한 값이 여러개 있어서 양쪽 끝에 이 값을 넣어둬야 AND연산 시에 동일한 값을 가질 수 있기 때문이다.

그래서 양쪽에 최솟값을 나열하는 경우 * 나머지 n - 2개를 나열하는 값이 맞다.
이 최솟값을 가지고 있는 원소도 있고 그렇지 않은 원소도 있다면 어떤 부분 배열의 경우 0이고 나머지는 최솟값을 가지고 있기 때문에 조건을 충족하지 않는다.

그래서 모든 원소가 최솟값을 가지고 있는지 AND연산을 했을 때 최솟값을 주는지를 확인해야 한다.

import sys
import math

t = int(sys.stdin.readline())
for _ in range(t):
    n = int(sys.stdin.readline())
    data = list(map(int, sys.stdin.readline().split()))

    val = min(data)
    cnt, flag = 0, 0

    for item in data:
        if val == item:
            cnt += 1
            continue

        if val & item != val:
            flag = 1
            break

    if flag:
        print(0)
        continue

    ans = cnt * (cnt - 1)
    for i in range(1, n - 1):
        ans = (ans * i) % int(math.pow(10, 9) + 7)

    print(ans)

0개의 댓글