OR

2021-08-10

字数统计: 1.1k字 | 阅读时长≈ 4分

题目大意

给定两个非负数组\(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;
}

本文作者： 水蓝络合物
本文链接： https://miku39393939.github.io/2021/08/10/OR/
版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！