MC0309魔法项链

思路：

以数位贡献的思路来写这题，

• 统计每一位上为 1 的个数：

  • 对于第 k 位，统计有多少个数在这一位上为 1，记作 cnts[k]

• 枚举每个数，逐位分析它对整体的贡献（即与其它数交互时的和）：

  • 如果第 k 位为 1：

    • & 中只有其他第 k 位为 1 的数才会产生贡献：共 cnts[k] - 1 个

    • | 中其他所有 n - 1 个数都可以贡献

    • 总和为：

      (1≪k)×((n−1)+(cnts[k]−1))

  • 如果第 k 位为 0：

    • & 无贡献

    • | 仅与第 k 位为 1 的数有贡献（共 cnts[k] 个）

    • 总和为：

      (1≪k)×cnts[k]

• 总贡献除以 2，避免重复计算每对 (i,j)

• 最后加上所有数本身的魔力值。

（数位贡献）

时间复杂度：O(n)

代码：

#include<bits/stdc++.h>
using namespace std;
using ll = long long;int main() {int n;cin >> n;vector<ll> a(n);vector<ll> cnts(30, 0);for (int i = 0; i < n; ++i) {cin >> a[i];for (int k = 0; k < 30; ++k) {if ((a[i] >> k) & 1) cnts[k]++;}}ll ans = 0;for (int i = 0; i < n; ++i) {for (int k = 0; k < 30; ++k) {if ((a[i] >> k) & 1) {ans += (1LL << k) * ((n - 1) + (cnts[k] - 1));} else {ans += (1LL << k) * cnts[k];}}}ans /= 2;  // 每对重复计算了两次for (ll val : a) ans += val;cout << ans << endl;return 0;
}