Apollo versus Pan(CF1466E)(位运算)

题意:
给定长度为 \(n\) 的序列 \(x\)。

\(\sum^{n}_{i=1} \sum^{n}_{j=1} \sum^{n}_{k=1} (x_{i}\ \& \ x_{j})\times (x_{j}\ |\ x_{k})\text{}\)


想法:

  • 首先进行化简:
    .

    \(\sum^{n}_{i=1} \sum^{n}_{j=1} \sum^{n}_{k=1} (x_{i}\ \& \ x_{j})\times (x_{j}\ |\ x_{k})\text{}\)

    .
    \(\Longrightarrow \sum^{n}_{j=1} \sum^{n}_{i=1} \sum^{n}_{k=1} (x_{i}\ \& \ x_{j})\times (x_{j}\ |\ x_{k})\text{}\)

    .
    \(\Longrightarrow \sum^{n}_{j=1} (\sum^{n}_{i=1} (x_{i\ }\& \ x_{j}))\times (\sum^{n}_{k=1} (x_{j}\ |\ x_{k})\text{} )\)

  • 从上面的式子中看得出来 \(j\) 是一定要枚举的,显然复杂度应该是不能是 \(O(n^2)\),那么可以想到枚举二进制位,也就是把 \(x_{i}\ \& \ x_{j}\) 的值通过对二进制位上拥有 \(1\) 的个数求出答案,因为 $x_{i}<2^{60} $,那么复杂度可以做到 \(O(60\times n)\)。

  • 我们可以预处理出整个序列在某一位上 \(1\) 的个数,从而避免对 \(i,k\) 的枚举。

  • 对 \(x_{i}\ \& \ x_{j}\),是这两个数某一位上都为 \(1\),最后答案才能加上这位 \(1\) 的贡献,\(x_{i}\ |\ x_{j}\) 只有有 \(1\) 即可加上贡献。


代码:

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int mod=1e9+7;
const int maxn=500005;


ll x[maxn];
ll cnt[105];

int main()
{
    int T,n;
    cin>>T;
    while(T--){
        memset(cnt,0,sizeof cnt);
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
            scanf("%lld",&x[i]);
            for(int j=0;j<=60;j++){
                if((1ll<<j)&x[i])cnt[j]++;
            }
        }
        ll ans=0;
        for(int i=1;i<=n;i++){
            ll base=1;
            ll num1=0,num2=0;
            for(int j=0;j<=60;j++){
                if((1ll<<j)&x[i]){
                    num1=(num1+base*cnt[j]%mod)%mod;
                    num2=(num2+base*n%mod)%mod;
                }else{
                    num2=(num2+base*cnt[j]%mod)%mod;
                }
                base=base*2%mod;
            }
            ans=(ans+num1*num2%mod)%mod;
        }
        cout<<ans<<endl;
    }
    return 0;
}

上一篇:百度造车和RoboTaxi利好自动驾驶?不,利好茅台


下一篇:自动驾驶 Apollo 源码分析系列,感知篇(一)