打卡记录

数对统计（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;
}