D OR
题意:给定你序列,其中。求符合条件的序列有多少种
首先:,定义,其中
可以看出,对的比特位值进行了限定。当我们给定时,可以依靠上述序列,直接确定后续的所有(),以此并反推给定的是否合法。所以我们去考虑枚举,依靠和,去位枚举的每一个数位,确定合法性并统计答案
对于任意位下,设为在连锁下确定的当前位为的可能。设,表示在递推确定时,序列前一位确定下来的数位是否能够为,设,表示当前序***定,当前这位是否能够为。则有下表:(牛客表格有问题就只能传图片了)
这里特别解释一下的情况:这个情况确定了和必有一个为,另一个为。
- 当时,需要,也就是唯一确定于
- 同理:当时,需要,唯一确定于上一个序***定的
每次递推时更新值,并统计结果即可
#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; }