The 13th UESTC Programming Contest Preliminary——Hug the princess

Programming Contest Preliminary——Hug the princess"/>

The 13th UESTC Programming Contest Preliminary——Hug the princess

题意：根据公式进行计算。

解题思路：首先，自己可以通过举几个例子来验证，异或运算与与运算之和刚好等价于或运算，或者可以这样想，异或是(1,0)、(0,1)，与是(1,1)，合起来刚好是或。然后题目就是求两倍的或运算了。然后，每一个ai都与aj或运算(i<j)，每次ai与aj或的时候，aj二进制位上是1的数位在或运算后总还是1，所以前面有多个ai与aj或，最后结果里就有多少个aj的和；然后考虑aj上是0的数位(比如第4位)，记录前面所有的ai中哪些数在这个第4位上是1，记为sum[4]，最后的结果里就有sum[4]*(1<<4)，因为有权值的。这样O(n)地扫一遍，就行了。

官方题解：

Code：

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;ll a[100005];
vector<ll> cnt;int main()
{int n;ll tn=0;scanf("%d",&n);for(int i=0;i<n;i++){scanf("%lld",&a[i]);tn=max(tn,a[i]);}ll ans=0,t=0;while(tn){t++;tn>>=1;cnt.push_back(0);}for(int i=0;i<n;i++){ans+=a[i]*i;for(int j=0;j<t;j++){if(!((a[i]>>j)&1))ans+=(1<<j)*cnt[j];elsecnt[j]++;}}printf("%lld\n",ans*2);return 0;
}