1.把字母轉成編號:
不能直接 減'A',因為會有小寫字母,在ascii碼上它們不是連續編號的,應該判斷大小寫,大寫則可以直接 減'A',小寫則 減'a'後再加26。
2. 二進制與位元運算:
有了字母編號後,就可以把一組CP轉化成二進制存進int了!先用bool陣列解釋會比較方便。
bool have[38]={0};
have[idx]=1; idx是字母轉成的編號,這就代表這組CP有idx這個字母,而要換成int表達的話,就需要用到位元運算
CP_num += (1LL<<idx); 1LL就是1,只不過是long long 的型態,一定要記得 LL 不然會溢位
然而這樣子如果CP的字母有重複的話,就會導致CP_num的二進制中 idx的位置進位而變成0
因此要避免重複加值的話,就改成 bitwise or
CP_num |= (1LL<<idx); 這樣就能避免重複加值了
而要找互補CP的方法就是用 bitwise xor
注意到如果兩個CP是互補的,則他們的 bitwise xor 的二進制就會是 111... m個1
而根據 bitwise xor 的性質 ( a^b=c,則 a^c=b ,^是bitwise xor在程式中的符號)
所以 a 的互補CP就是 (111... m個1) ^ a
而 111... m個1 最快速的生成方法就是 (1LL<<m) - 1
這是二進制的特性,m個1代表在十進位中這個數字的值是 2**0 + 2**1 + 2**2 + ... + 2**(m-1) (**是次方的意思)
可以很容易的用等比級數公式證明 m個1就會等於 2**m-1
3. 排序與二分搜
將每個CP_num存進一個陣列裡,再sort這個陣列(為了二分搜)
最後 ans += upper_bound( arr, arr+n, arr[i]^( (1LL<<m) - 1) ) - lower_bound( arr, arr+n, arr[i]^( (1LL<<m) - 1) )
把每個arr[i]有幾個互補CP加進ans,因為每組會重複算到一次,所以答案是 ans>>1
1.把字母轉成編號:
不能直接 減'A',因為會有小寫字母,在ascii碼上它們不是連續編號的,應該判斷大小寫,大寫則可以直接 減'A',小寫則 減'a'後再加26。
2. 二進制與位元運算:
有了字母編號後,就可以把一組CP轉化成二進制存進int了!先用bool陣列解釋會比較方便。
bool have[38]={0};
have[idx]=1; idx是字母轉成的編號,這就代表這組CP有idx這個字母,而要換成int表達的話,就需要用到位元運算
CP_num += (1LL<
然而這樣子如果CP的字母有重複的話,就會導致CP_num的二進制中 idx的位置進位而變成0
因此要避免重複加值的話,就改成 bitwise or
CP_num |= (1LL<
而要找互補CP的方法就是用 bitwise xor
注意到如果兩個CP是互補的,則他們的 bitwise xor 的二進制就會是 111... m個1
而根據 bitwise xor 的性質 ( a^b=c,則 a^c=b ,^是bitwise xor在程式中的符號)
所以 a 的互補CP就是 (111... m個1) ^ a
而 111... m個1 最快速的生成方法就是 (1LL<
這是二進制的特性,m個1代表在十進位中這個數字的值是 2**0 + 2**1 + 2**2 + ... + 2**(m-1) (**是次方的意思)
可以很容易的用等比級數公式證明 m個1就會等於 2**m-1
3. 排序與二分搜
將每個CP_num存進一個陣列裡,再sort這個陣列(為了二分搜)
最後 ans += upper_bound( arr, arr+n, arr[i]^( (1LL<
把每個arr[i]有幾個互補CP加進ans,因為每組會重複算到一次,所以答案是 ans>>1
最後一步可以不用二分搜,用雙指針,
while( i<j ) {
y = (1LL << m) - 1 - x ;
i由前往後先統計x值個數a;
j由後往前統計y值個數b;
ans += a*b;
}