1513-B, *1400

Problem - 1513B - Codeforces

문제

• 수열 $a_{1}a_{2}...a_{n}$이 주어질 때, 다음 조건을 만족시키는 수열 $a_{p_{1}}a_{p_{2}}...a_{p_{n}}$의 개수?
• $a_{p_{1}}\& a_{p_{2}}\&\cdot \cdot \cdot \& a_{p_{i}} = a_{p_{i+1}}\& a_{p_{i+2}}\&\cdot \cdot \cdot \& a_{p_{n}}(1\leq i < n)$ ... !

 

$O(nlog\ n)$

bitwise operation인 &가 이용되므로
비트의 각 자리수마다 조건 ! 을 만족하는 집합을 각각 구한뒤 그것들의 교집합을 이용하면 되겠다
ex)
01(2), 11(2) 가 주어졌다고 하면
오른쪽부터 1번째 비트만 생각했을 때 조건 !을 만족하는 경우 A,
오른쪽부터 2번째 비트만 생각했을 때 조건 !을 만족하는 경우 B
구하려고 하는건 $\mathrm{A\cap B}$

이때 $i$번째 비트들은 다음 세가지 중 하나이다
i) 0 이 없음
- 모든 순열이 !을 만족한다 ~ $\mathrm{Set = Universe}$
ii) 0 이 한개
- 어떠한 순열도 !을 만족시키지 않는다 ~ $Set =  \emptyset$
iii) 0 이 두개 이상
- $a_{p_{1}}=0,\ a_{p_{n}}=0$만 성립하면 된다 ~ $\mathrm{\left | Set \right |}=(n-2)!_{\mathrm{(0\ bit\ number)}} P_{2}$

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
typedef long long ll;
 
int n;
int mod = 1e9+7;
int arr[200001] {};
 
int bit_cnt(int n)
{
    int cnt = 0;
    while(n > 0){
        cnt++;
        n >>= 1;
    }
    return cnt;
}
 
ll calculate(ll side)
{
    if(side < 2) return 0;
    ll res = side*(side-1)%mod;
    loop(i, n-2) res = res*i%mod;
    return res;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        cin >> n;
        int maxbit = 0;
        loop(i, n){
            cin >> arr[i];
            if(arr[i] > maxbit) maxbit = arr[i];
        }
        maxbit = bit_cnt(maxbit);
 
        bitset<200001> side;
        int cmp = 1;
        loop(i, maxbit){
            bool isallone = true;
            loop(j, n){
                if((cmp & arr[j]) == 0) isallone = false;
            }
            if(!isallone) {
                loop(j, n) side[j] = (cmp & arr[j]) || side[j];
            }
            cmp *= 2;
        }
 
        int one = side.count();
        cout << calculate(n-one) << endl;
 
    }
 
    return 0;
}cs

 

$O(n)$

Claim1
$$For\ a,\ b \in \mathbb{N},\ a\& b \leq a$$

$\because$
& 의 정의에 의해
a & b 는 a에서 0인 bit 는 모두 0이고, 1인 bit는 1 이거나 0 이다□

 

Claim2
$Pref_{i} = a_{p_{1}}\& a_{p_{2}}\& \cdot \cdot \cdot \& a_{p_{i}},\ Subf_{i} = a_{p_{i}}\& a_{p_{i+1}}\& \cdot \cdot \cdot \& a_{p_{n}}$ 라고 할때
$$\begin{align*} \mathrm{(Sequence\ \left \{ a_{p} \right \}\ sadisfies\ condition\ !)  } \Leftrightarrow Pref_{1}&=Pref_{2}=\cdot \cdot \cdot = Pref_{n-1}\\                         &=Subf_{2}=\cdot \cdot \cdot = Subf_{n-1}=Subf_{n} \end{align*}$$

$\because$
($\Leftarrow$)
$\mathrm{condition\ !} \Leftrightarrow Pref_{i}=Subf_{i+1}\ for\ i = 1,\ 2,\ ...,\ n-1$

$(\Rightarrow)$
$\begin{align*} &Pref_{2}\leq Pref_{1}(\because \text{Claim1})\\ &Pref_{1}=Subf_{2}(\because \text{Condition !})\\ &Subf_{2} \leq Subf_{3}(\because \text{Claim1})\\ &\Leftrightarrow Pref_{2}\leq Pref_{1}=Subf_{2} \leq Subf_{3}\\ &\Rightarrow Pref_{2}=Pref_{1}=Subf_{2}=Subf_{3}(\because Pref_{2}=Subf_{3}) \end{align*}$

같은 논리를 반복□

 

Claim3
$$\begin{matrix} Pref_{1}=Pref_{2}=\cdot \cdot \cdot = Pref_{n-1}\\ \quad \quad \quad \quad \quad \quad \ \ =Subf_{2}=\cdot \cdot \cdot = Subf_{n-1}=Subf_{n} \end{matrix} \Leftrightarrow \begin{matrix} a_{p_{1}}=a_{p_{n}}\ \mathrm{is\ minimum\ element\ of\ \left \{ a_{p} \right \}}\\ a_{p_{1}}\& a_{p_{i}}=a_{p_{1}}\ \mathrm{for\ i=2,\ 3,\ ...,\ n} \quad \quad \ \ \end{matrix}$$

$\because$
($\Rightarrow$)
$\left\{\begin{matrix} \begin{aligned} &a_{p_{1}}\& a_{p_{2}}=a_{p_{1}}(\because Pref_{1}=Pref_{2})\\ &a_{p_{1}}\& a_{p_{2}}\leq a_{p_{1}},\ a_{p_{1}}\& a_{p_{2}}\leq a_{p_{2}} \Rightarrow a_{p_{1}}\& a_{p_{2}}\leq \mathrm{min(a_{p_{1}},\ a_{p_{2}})}\\ \end{aligned} \end{matrix}\right. \Rightarrow \mathrm{min(a_{p_{1}},\ a_{p_{2}})\ =a_{p_{1}}\ i.e.\ a_{p_{1}}\leq a_{p_{2}}}$

$\left\{\begin{matrix} \begin{aligned} &a_{p_{1}}\& a_{p_{3}}=a_{p_{1}}(\because Pref_{1}=Pref_{2},\ Pref_{2}=Pref_{3})\\ &a_{p_{1}}\& a_{p_{3}}\leq a_{p_{1}},\ a_{p_{1}}\& a_{p_{3}}\leq a_{p_{3}} \Rightarrow a_{p_{1}}\& a_{p_{3}}\leq \mathrm{min(a_{p_{1}},\ a_{p_{3}})}\\ \end{aligned} \end{matrix}\right. \Rightarrow \mathrm{min(a_{p_{1}},\ a_{p_{3}})\ =a_{p_{1}}\ i.e.\ a_{p_{1}}\leq a_{p_{3}}}$

동일한 논리로 $\mathrm{for\ all}\ i, a_{p_{1}}\leq a_{p_{i}}$
또한 $a_{p_{1}}\& a_{p_{i}}=a_{p_{1}}\ \mathrm{for\ i=2,\ 3,\ ...,\ n}$도 증명되었다

($\Leftarrow$)
$Pref_{1}=a_{p_{1}}$
$Pref_{2}=a_{p_{1}}\& a_{p_{2}}=a_{p_{1}}$
$\begin{aligned} Pref_{3}&=(a_{p_{1}}\& a_{p_{2}})\& a_{p_{3}}\\ &=a_{p_{1}}\&a_{p_{3}}\\ &=a_{p_{1}} \end{aligned}$

동일한 논리로 $a_{p_{1}}=Pref_{1}=\cdot \cdot \cdot = Pref_{n-1}=Subf_{2}=\cdot \cdot \cdot =Subf_{n}=a_{p_{n}}$□

#include <bits/stdc++.h>
#define endl "\n"
#define loop(i, n) for(int i = 1; i <= n; i++)
using namespace std;
 
int n;
int mod = 1e9+7;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
 
    int t;
    cin >> t;
    while(t--){
        cin >> n;
        vector<int> v(n);
        for(int i = 0; i < n; i++) cin >> v[i];
 
        int minval = *min_element(v.begin(), v.end());
        int cnt = 0;
        for(auto e: v){
            if((e & minval) != minval) {
                cnt = 0;
                break;
            }
            if(minval == e) cnt++;
        }
 
        if(cnt >= 2){
            int res = 1LL*cnt*(cnt-1)%mod;
            loop(i, n-2) res = 1LL*res*i%mod;
            cout << res << endl;
        }
        else cout << 0 << endl;
 
    }
 
    return 0;
}cs

※ long long value_name = (expression)
- 변수를 사용하는 식은 expression 도 long long 변수가 사용되어야 한다
- mod 연산으로 expression이 long long 에서 int 이내로 변환될 때 1LL 사용할것
※ break 문이 위쪽에 있는것이 좋다