Codeforces Round #379 (Div. 2) F. Anton and School

题目链接

分析：这道题的关键点是要知道一个关于位运算的式子

a+b=(a|b)−(a & b)

这样的话，可以有以下的推导： ∑ni=1a[i]=sum ，那么 c[i]=∑Nj=1(a[i]+a[j])−b[i] ，然后推出 b[i]+c[i]=N∗a[i]+sum ，可以计算出 a[i]

还有一点需要注意，就是验证一下 a[i] 的正确性。这里也是要小技巧的。将整个式子拆成二进制的形式进行与和或的操作，这样能把长度为N的和式在 O(1) 的时间内求出来。

/*****************************************************/
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <map>
#include <set>
#include <ctime>
#include <stack>
#include <queue>
#include <cmath>
#include <string>
#include <vector>
#include <cstdio>
#include <cctype>
#include <cstring>
#include <sstream>
#include <cstdlib>
#include <iostream>
#include <algorithm>

using namespace std;

#define   offcin        ios::sync_with_stdio(false)
#define   sigma_size    26
#define   lson          l,m,v<<1
#define   rson          m+1,r,v<<1|1
#define   slch          v<<1
#define   srch          v<<1|1
#define   sgetmid       int m = (l+r)>>1
#define   ll            long long
#define   ull           unsigned long long
#define   lowbit(x)     (x&-x)
#define   bits(a)       __builtin_popcount(a)

const int    INF    = ;
const ll     INFF   = ;
const double pi     = acos(-);
const double inf    = ;
const double eps    = ;
const ll     mod    = +;
const int    maxmat = ;
const ull    BASE   = ;

/*****************************************************/
inline void RI(int &x) {
      char c;
      while((c=getchar())<'0' || c>'9');
      x=c-'0';
      while((c=getchar())>='0' && c<='9') x=(x<<)+(x<<)+c-'0';
}
/*****************************************************/

const int maxn =  + ;

ll a[maxn], b[maxn], c[maxn];
int cnt[];

int main(int argc, char const *argv[]) {
    int N; cin>>N;
    ll sum = ;
    for (int i = ; i <= N; i ++) cin>>b[i], sum += b[i];
    for (int i = ; i <= N; i ++) cin>>c[i], sum += c[i];
    if (sum % ( * N)) {puts("-1"); return ;}
    sum = sum / N / ;
    for (int i = ; i <= N; i ++) {
        if ((b[i] + c[i] - sum) % N) {puts("-1"); return ;}
        a[i] = (b[i] + c[i] - sum) / N;
    }
    for (int i = ; i <= N; i ++)
        for (int j = ; j < ; j ++)
            cnt[j] += a[i] >> j & ;
    for (int i = ; i <= N; i ++) {
        ll bb = , cc = ;
        for (int j = ; j < ; j ++)
            if (a[i] >> j & ) bb += cnt[j] * (l << j), cc += N * (l << j);
            else cc += cnt[j] * (l << j);
        if (bb != b[i] || cc != c[i]) {puts("-1"); return ;}
    }
    for (int i = ; i <= N; i ++) cout<<a[i]<<" ";
    return ;
}