题解-CF734F

本文章遵守知识共享协议 CC-BY-NC-SA，同步发表于洛谷题解区，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

一道……构造题？

题目大意

有一个数列 $A$，通过 $A$ 构造出数列 $B$ 和 $C$，其中 $B_i = \sum_{k=1}^n A_i \operatorname{and} A_k$，$C_i = \sum_{k=1}^n A_i \operatorname{or} A_k$，现在给定 $B$ 和 $C$，要求你给出任意一组合法的 $A$ 或报告无解。

解题思路

要解这个题，我们首先要观察到这样一个性质：

$a \operatorname{or} b = \sum_{i=0}2^i \max(a_i,b_i),a \operatorname{and} b = \sum_{i=0}2^i\min(a_i,b_i)$（$a_i$ 和 $b_i$ 是数的二进制拆分低 $i$ 位）

那我们不难发现：

插一嘴：这里和 $\gcd(a,b)\operatorname{lcm}(a,b) = ab$ 有异曲同工之妙。

回归正题，我们将 $B$ 与 $C$ 逐项相加，得出来的式子如下：

于是我们可以将所有的项加起来：

我们就得到了每一项的总和，将上面构造的项依次减去它即可。

无解的情况就是要除的部分整除不了。

还有就是，在构造出原序列之后，我们还需要通过原序列构造出 $A$ 数列，来二次检验答案的正确性（hack:1 3 5）。

那我们如何快速计算呢？这里考虑按位计算贡献。当且仅当 $a$ 和 $b$ 的二进制第 $i$ 位同为 $1$ 时才会对答案造成 $2^i$ 的贡献。

所以我们按位统计贡献即可，复杂度线对。

#include <stdio.h>
#include <vector>

typedef long long i64;
const i64 mod = 1, maxn = 200007;

i64 li[maxn], n, u, v, diff, flg1, d, c1, sum, cnt[65], a[maxn], b[maxn], c[maxn];

int main()
{
    scanf("%d", &n);

    for (int i = 1; i <= n; i++)
        scanf("%d", &u), a[i] += u, li[i] += u;
    for (int i = 1; i <= n; i++)
        scanf("%d", &u), b[i] += u, li[i] += u;
    for (int i = 1; i <= n; i++)
        sum += li[i];

    if (sum % (2 * n))
        return puts("-1") & 0;
    sum /= (2 * n);

    for (int i = 1; i <= n; i++)
        if ((li[i] - sum) % n)
            return puts("-1") & 0;
        else
            c[i] = (li[i] - sum) / n;

    for (int i = 1; i <= n; i++)
        for (int bit = 0; bit < 30; bit++)
            if (c[i] & (1ll << bit))
                cnt[bit]++;

    for (int i = 1; i <= n; i++)
    {
        i64 res = 0;
        for (int bit = 0; bit < 30; bit++)
            if (c[i] & (1ll << bit))
                res += (1ll << bit) * cnt[bit];
        if (res != a[i])
            return puts("-1") & 0;
    }

    for (int i = 1; i <= n; i++)
        printf("%d ", c[i]);

    return 0;
}