D OR

链接：D-OR_2021牛客暑期多校训练营8 (nowcoder.com)
题意：给定你序列 $b_i = a_{i-1} |a_i,\ c_i = a_{i-1} + a_i$ ，其中 $2\le i \le n$ 。求符合条件的 $a_i$ 序列有多少种
首先： $c_i = a_{i-1} + a_i = a_{i-1} | a_i + a_{i-1} \& a_i$ ，定义 $d_i = a_{i-1} \& a_i = c_i - b_i$ ，其中 $2\le i \le n$
可以看出， $b_i, d_i$ 对 $a_i$ 的比特位值进行了限定。当我们给定 $a_1$ 时，可以依靠上述序列，直接确定后续的所有 $a_i$ （ $2\le i \le n$ ），以此并反推给定的 $a_1$ 是否合法。所以我们去考虑枚举 $a_1$ ，依靠 $b_i$ 和 $d_i$ ，去位枚举 $a_1$ 的每一个数位，确定合法性并统计答案
对于任意位下，设 $nowbit$ 为在连锁下确定的当前位为 $0,1$ 的可能。设 $bit0,bit1$ ，表示在递推确定时，序列前一位确定下来的数位是否能够为 $0,1$ ，设 $nowbit0,nowbit1$ ，表示当前序***定，当前这位是否能够为 $0, 1$ 。则有下表：（牛客表格有问题就只能传图片了）
这里特别解释一下 $b_i = 1,d_i = 0$ 的情况：这个情况确定了 $a_{i-1}$ 和 $a_i$ 必有一个为 $1$ ，另一个为 $0$ 。
- 当 $a_{i} = 0$ 时，需要 $a_{i-1} = 1$ ，也就是 $nowbit0$ 唯一确定于 $bit1$
- 同理：当 $a_{i} = 1$ 时，需要 $a_{i-1} = 0$ ， $nowbit1$ 唯一确定于上一个序***定的 $bit0$
每次递推时更新值，并统计结果即可

#include <bits/stdc++.h>
#define endl '\n'
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
const int N = 1e5 + 7;
ll b[N], c[N], d[N];
signed main() {
    int n;
    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];
    ll ans = 1;
    for(int i = 0; i <= 31; ++i) {
        int bit0 = 1, bit1 = 1;//初始默认前面0，1均可取
        for(int j = 2; j <= n; ++j) {
            int nowbit0 = 0, nowbit1 = 0;
            int x = b[j] >> i & 1;
            int y = d[j] >> i & 1;
            if(!x && !y) nowbit0 = bit0;
            else if(x && !y) nowbit1 = bit0, nowbit0 = bit1;
            else if(x && y)  nowbit1 = bit1;
            bit1 = nowbit1, bit0 = nowbit0;//确定当前数位状态
        }ans *= bit1 + bit0;//更新结果
    }printf("%lld\n", ans);
    return 0;
}

题解 | #D OR#

D OR