2021牛客暑期多校训练营8 D、OR

题目大意

你原本有个长度为的序列，现在我只告诉你两个长度为的序列，问合理的序列有多少种？

我们定义。

Solution

由于给出的数组都是位运算得来的，我们就可以按位拆分，枚举的每一位，再去枚举不同的数。

我们首先看最低位，注意下面的代表着当前枚举的这一位二进制是还是，同理，映射到题目就是：

如果在最低位的情况下，这样的一共有个说明我们这一位存在两种构建方法，即或者这样交替进行。

我们把不足位我们可以分成下面的情况。

如果在最低位的某一个，说明它一定产生了进位，那么我们就把这次产生的进位消除，当我们每次都消除进位的时候就可以一直当作最低位处理了，例如，在我们消除最低位的带来的影响后它的第二位第三位都可以看作新的最低位处理了。

如果在最低位的某一个这一定是非法的，因为最低位不可能有来自进位的。

如果在最低位的某一个，我们就看它进位是不是来自如果是刚刚前两个的话说明当前的这个不可能是，一定会存在一个让它进位。那么其余合法的时候例如后面跟一个这是合法的，但是出现了这样的进位说明当前这一位我们也只有一种构造序列的方法。

const int N = 1e5 + 7;
ll n, m;
int b[N], c[N];

int solve() {
    n = read();
    for (int i = 1; i < n; ++i)    b[i] = read();
    for (int i = 1; i < n; ++i)    c[i] = read();

    for (int i = 1; i < n; ++i) {
        if (b[i] > c[i]) {
            return print(0), 1;
        }
    }

    ll res = 1;
    for (int i = 0; i < 34; ++i) {
        int cnt = 0, pos = -100;
        for (int j = 1; j < n; ++j) {
            int bit1 = b[j] >> i & 1, bit2 = c[j] >> i & 1;
            if (bit1 == 1 && bit2 == 1)    ++cnt;
            else if (bit1 == 1 && bit2 == 0) {
                c[j] -= (1ll << i);
                pos = j;
            }
            else if (bit1 == 0 && bit2 == 1) {
                return print(0), 0;
            }
            else if (bit1 == 0 && bit2 == 0) {
                if (pos == j - 1) {
                    return print(0), 0;
                }
            }
        }
        if (cnt == n - 1)    res *= 2;
    }
    print(res);


    return 1;
}