Day56力扣打卡

打卡记录

数对统计（DP状态压缩）

参考文献

#include <bits/stdc++.h>


using namespace std;


void solve(){
   
    int n;
    cin >> n;

    map<int, int> mapp;
    vector<int> a(n);
    for (auto& x : a){
   
        cin >> x;
        mapp[x] ++;
    }

    vector<array<long long, 20>> dp(1 << 20);
    int mask = (1 << 20) - 1;
    for (int i = 0; i <= mask; ++i){
   
        if (i & 1){
   
            dp[i][0] = mapp[i] + mapp[i ^ 1];
        }
        else{
   
            dp[i][0] = mapp[i];
        }
        for (int j = 1; j < 20; ++j){
   
            if ((i >> j) & 1){
   
                dp[i][j] = dp[i][j - 1] + dp[i ^ (1 << j)][j - 1];
            }
            else{
   
                dp[i][j] = dp[i][j - 1];
            }
        }
    }

    long long ans = 0;
    for (auto& x : a){
   
        ans += dp[mask ^ x][19];
    }

    cout << ans << '\n';

}



int main(){
   
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int tc = 1;




   // cin >> tc;

    while (tc--){
   
        solve();
    }

    return 0;
}