B. AND Sequences

https://codeforces.com/contest/1513/problem/B

문제

양수로 이루어진 수열 $a_1, a_2, ... , a_n$이
$1 <= i <= n$인 모든 $i$ 에 대해,
$a_1 \& a_2 \&... \& a_i = a_{i+1} \& a_{i+2} \&... \& a_n$ 을 만족할 때
이 수열을 "좋은 수열"이라고 하자.
길이가 n인 임의의 수열이 주어질때, "좋은 수열"이 될 수 있는 permutaion의 개수를 구하라.

풀이

이 문제의 key point는 &를 하고 나면 숫자가 작아지는 것이다.
즉, $a \& b <= a$이다.
$a_1, ... , a_n$이 "좋은 수열"이라고 하자.
$\begin{aligned} a_1 &= a_2 \& a_3 \&... \& a_n \\ &\le a_3 \& a_4 \&... \& a_n \\ &\le ... \\ &\le a_n \end{aligned}$

$\begin{aligned} a_n &= a_1 \& a_2 \&... \& a_{n-1} \\ &\le a_1 \& a_2 \&... \& a_{n-2} \\ &\le ... \\ &\le a_1 \end{aligned}$

즉, $a_1 = a_n$이고, 그 사이의 모든 항들은 다 $a_1$과 값이 같다.

수열이 주어지면 가장 작은 값 x를 구하고, x의 개수가 2이상인지 확인한다.
x가 아닌 다른 모든 수 y에 대해, x & y = x인지 확인한다.
두 가지 조건을 통과했으면, 순열의 개수를 구하면 된다.