题解 | #D Or#_牛客博客

站在巨人的肩膀上写出了这篇题解
有错误也欢迎各路dalao帮指出orz

题目大意

给定两个非负数组 $b[2...n],c[2...n]$ ，构造出数组 $a[1...n]$ 满足： $a[i-1]|a[i] = b[i],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|b)+(a\&b)$

很好验证，那么

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

=> $c[i] = (a[i-1] | a[i]) + (a[i-1]\&a[i])$

=> $c[i] = b[i] + (a[i - 1] \& a[i])$

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

=> $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]|a[i-1],d[i] = a[i-1]\&a[i-1]$ 。

那么无非是这三种情况：

$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; //第j个数的第i位
            if(x == 0 && y == 0)    //上一个数能为0，那这个数也能为0，（这一位不能为1了，所以nowBit1就还是0）
                nowBit0 = preBit0; //如果上一个数不能为0，那么显然就不合法了，那么对答案的贡献就是0了。
            if(x == 0 && y == 1) {
                nowBit0 = preBit1;
                nowBit1 = preBit0;
            }
            if(x == 1 && y == 1)
                nowBit1 = preBit1;//上一个数能为1，那这个数也能为1，（这一位不能为1了，所以nowBit0就还是0）
            preBit0 = nowBit0;
            preBit1 = nowBit1;
        }
        ans *= preBit0 + preBit1;
    }
    printf("%lld\n",ans);
    return 0;
}

题解 | #D Or#

题目大意

思路

具体做法

代码