【牛客竞赛】Or题解

题目大意

给定两个非负数组 $b[2\ldots n], c[2\ldots n]$，构造出数组 $a[1\ldots n]$ 满足：

$$a[i-1] \mid a[i] = b[i],\quad a[i-1] + a[i] = c[i]$$

求出满足要求的数组 $a$ 的数量。（$1 \le n \le 10^5,\ 1 \le b[i], c[i] \le 10^9$）

题目链接

思路

直接枚举 $a[1]$ 然后检测的话，会TLE，因为每一位都有两种选择，且由于 $c$ 数组的存在，导致二进制下的每一位都不是独立的（因为有进位的存在）。比如我们认为答案可能在000~111（二进制下）之间。我们必须从000一直枚举到111。

假如我们可以让每一位都独立的话，就可以单独检验 $a[1]$ 每一位是否可以为0或1。

事实上，加法运算有一个位运算的转化（这个不知道大概就寄了，比如我）

$$a + b = (a \mid b) + (a \mathbin{\&} b)$$

很好验证，那么

$c[i] = a[i-1] + a[i]$

$\Rightarrow\ c[i] = (a[i-1] \mid a[i]) + (a[i-1] \mathbin{\&} a[i])$

$\Rightarrow\ c[i] = b[i] + (a[i-1] \mathbin{\&} a[i])$

令 $d[i] = a[i] \mathbin{\&} a[i-1]$

$\Rightarrow\ d[i] = c[i] - b[i]$

现在我们有 $b, d$ 两个数组了，注意 $d$ 和 $b$ 的区别：$b$ 数组是通过加法运算来限制 $a$ 数组的，而 $d$ 数组是通过”按位与”运算来限制 $a$ 数组的，是没有进位操作的，所以对于d数组，二进制下每一位是相互独立的。

也就是说，因为每一位是相互独立的，我们可以单独枚举每一位的可能值，然后用乘法原理把结果相乘。

比如我们认为答案可能在000到111之间，那么我们只用枚举第一位是否可以为0、1，第二位是否可为0、1，第三位可否为0、1，然后把结果数量相乘即可。

那么如何验证呢？

对于每一位，都有 $b[i] = a[i] \mid a[i-1],\ d[i] = a[i-1] \mathbin{\&} a[i]$。

那么无非是这三种情况：

• $b[i]$ 这一位是 $1$，$d[i]$ 这一位是 $1$，那么 $a[i], a[i-1]$ 这一位必须是1。
• $b[i]$ 这一位是 $1$，$d[i]$ 这一位是 $0$，那么 $a[i]$ 这一位可以为 $0$ 的前提就是 $a[i-1]$ 这一位可以为 $1$，同理，$a[i]$ 这一位可以为 $1$ 的前提就是 $a[i-1]$ 这一位可以为 $0$。（它们或起来为1，与起来为0，那么肯定一个1一个0）
• $b[i]$ 这一位是 $0$，$d[i]$ 这一位是 $0$，那么显然 $a[i], a[i-1]$ 均为0。
• 怎么会有两个数与起来为 $1$ 但是或起来为 $0$ 呢

具体做法

我们求出 $d$ 数组后，按位枚举，对于每一位枚举 $a[1]$ 第 $i$ 位是否可以为0、1，然后对于每一个数 $j$ 进行检验。

检验时，用preBit0表示上一个数的这一位（即 $a[j-1]$ 的第 $i$ 位）可否为0，用preBit1表示上一个数的这一位可否为1（0为不可以，1为可以）。

用nowBit0表示这个数的这一位（即 $a[j]$ 的第 $i$ 位）可否为0，nowBit1表示这个数的这一位可否为1。

然后进行递推即可。

代码

#include <cstdio>
#include <iostream>
using namespace std;

const int maxN = 1e5 + 7;

long long b[maxN], c[maxN], d[maxN];
int n;

int main()
{
    scanf("%d", &n);
    for(int i = 2; i <= n; ++i)
        scanf("%lld", &b[i]);
    for(int i = 2; i <= n; ++i)
        scanf("%lld", &c[i]);
    for(int i = 2; i <= n; ++i)
        d[i] = c[i] - b[i];
    long long ans = 1;
    for(int i = 0; i <= 31; ++i) {
        int preBit0 = 1, preBit1 = 1;
        for(int j = 2; j <= n; ++j) {
            int nowBit0 = 0, nowBit1 = 0;
            int x = d[j] >> i & 1, y = b[j] >> i & 1;
            if(x == 0 && y == 0)
                nowBit0 = preBit0;
            if(x == 0 && y == 1) {
                nowBit0 = preBit1;
                nowBit1 = preBit0;
            }
            if(x == 1 && y == 1)
                nowBit1 = preBit1;
            preBit0 = nowBit0;
            preBit1 = nowBit1;
        }
        ans *= preBit0 + preBit1;
    }
    printf("%lld\n",ans);
    return 0;
}