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

题目大意

你原本有个长度为 $n(2\le n\le10^5)$ 的序列 $a_i$ ，现在我只告诉你两个长度为 $n-1$ 的序列 $b_i,c_i$ ，问合理的 $a_i$ 序列有多少种？

我们定义 $b_i=a_{i-1}\ \mathbf{or}\ a_i,c_i=a_{i-1}+a_i$ 。

Solution

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

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

如果在最低位的情况下， $b_j=1,c_j=1$ 这样的 $j$ 一共有 $n-1$ 个说明我们这一位存在两种构建方法，即 $010101$ 或者 $101010$ 这样交替进行。

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

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

如果在最低位的某一个 $b_j=0,c_j=1$ 这一定是非法的，因为最低位不可能有来自进位的 $1$ 。

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

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;
}