2021牛客多校训练营8

D

题意描述

有两个长度为\(n - 1\)的整数序列\(b=\{b_{2},b_{3}...b_{n}\}\),\(c=\{c_{2},c_{3}...c_{n}\}\)，其中\(b_{i}=a_{i-1} \ | \ a_{i}\)，\(c_{i}=a_{i-1}+a_{i}\)，求满足该条件的\(a\)序列的个数

思路

由于\(a|b=a+b-a\&b\)，所以\(c[i]-b[i]=a_{i}\&a_{i-1}=d_{i}\)。此时我们就得到了\(a_{i}\)的两个限制，由于每一位都是独立的且确定了\(a_{1}\)我们就能得到整个\(a\)序列，所以我们可以枚举\(a_{1}\)的每一位来进行判断。
定义\(lstbit0\)为上一位是0的状态，有两种取值\(0/1\)(下面定义的都是这两种取值),为\(0\)表示不能为\(0\)，为\(1\)表示可以为\(0\)，\(lstbit1\)表示上一位是1的状态，\(nowbit1\)表示当前位为\(1\)的状态，\(nowbit0\)表示当前位为\(0\)的状态，则当前位的贡献则为\(bit0+bit1\)。我们列出一个表格如下：

代码

#include 

using ll = long long;
const int N = 1e5 + 5;
int a[N], b[N], c[N], n, d[N];

void solve()
{
    std::cin >> n;
    for(int i = 2; i <= n; ++i) std::cin >> b[i];
    for(int i = 2; i <= n; ++i) std::cin >> c[i];
    for(int i = 2; i <= n; ++i) d[i] = c[i] - b[i];
    ll ans = 1;
    for(int i = 0; i < 32; ++i)
    {
        int bit0 = 1, bit1 = 1;
        for(int j = 2; j <= n; ++j)
        {
            int nowbit0 = 0, nowbit1 = 0;
            int x = b[j] >> i & 1, y = d[j] >> i & 1;
            if(!x && !y) nowbit0 = bit0;
            else if(x && !y) nowbit0 = bit1, nowbit1 = bit0;
            else if(x && y) nowbit1 = bit1;
            bit0 = nowbit0, bit1 = nowbit1;
        }
        ans *= (bit0 + bit1);
    }
    std::cout << ans << '\n';
}

int main()
{

    std::ios::sync_with_stdio(false);
    std::cin.tie(0);
    std::cout.tie(0);
    int t = 1;
    while(t--) solve();

}