2021牛客多校第八場 D

賽場上有一個公式沒推出來。

a + b = (a | b) + (a & b)

有了這個公式後直接對于每一個數字來說按位枚舉情況，然後找方案數即可。過程中會有回溯去修改曆史情況的值。

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 100010;
#define ll long long

int n;
int b[N], c[N], d[N];
int a[N][32];

int main() {
	scanf("%d", &n);
	for(int i = 2;i <= n;i ++) {
		scanf("%d", &b[i]);
	}
	for(int i = 2;i <= n;i ++) {
		scanf("%d", &c[i]);
		d[i] = c[i] - b[i];
	}

	int has_ans = 1;
	for(int i = 0;i < 31;i ++) {
		for(int j = 1;j <= n;j ++) {
			if(j == 1) {
				if((b[j+1]&1)==1&&(d[j+1]&1)==1) a[j][i] = 1, a[j+1][i] = 1;
				else if((b[j+1]&1)==0&&(d[j+1]&1)==1) has_ans = 0;
				else if((b[j+1]&1)==1&&(d[j+1]&1)==0) a[j][i] = 2, a[j+1][i] = 2;
				else a[j][i] = 0, a[j+1][i] = 0;
			}
			else {
				if((b[j]&1)==1&&(d[j]&1)==1) {
					if(a[j][i] == 2) {
						int v = 0, y = j;
						a[j][i] = a[j + 1][i] = 1;
						while(-- y >= 0 && a[y][i] == 2) {
							a[y][i] = v;
							v ^= 1;
						}
					}
					else if(a[j][i] == 0) has_ans = 0;
					else a[j+1][i] = 1;
				}
				else if((b[j]&1)==0&&(d[j]&1)==1) has_ans = 0;
				else if((b[j]&1)==1&&(d[j]&1)==0) {
					a[j+1][i] = 2;
				}
				else {
					if(a[j][i] == 2) {
						int v = 1, y = j;
						a[j+1][i] = a[j][i] = 0;
						while(-- y >= 0 && a[y][i] == 2) {
							a[y][i] = v;
							v ^= 1;
						}
					}
					else if(a[j][i] == 1) has_ans = 0;
					else a[j+1][i] = 0;

				}
			}
			b[j] >>= 1;
			d[j] >>= 1;
		}
	}

	ll ans = 1;
	for(int i = 0;i < 31;i ++)
		if(a[1][i] == 2) ans = ans * 2;

	if(has_ans) printf("%d\n", ans);
	else printf("0\n");

	return 0;
}