题目
时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 262144K，其他语言524288K 64bit IO Format: %lld
题目描述
There are two sequences of length n-1n−1, b=(b_2,b_3,\ldots,b_n)b=(b2,b3,…,b**n), c=(c_2,c_3,\ldots,c_n)c=(c2,c3,…,c**n). Here, each b_ib**i,c_ic**i is a non-negative integer.
Now, the sequence a=(a_1,a_2,\ldots,a_n)a=(a1,a2,…,a**n) considers beautiful if and only if forall ii (2 \leq i \leq n)(2≤i≤n), b_i = a_{i-1} , \text{or} , a_{i}b**i=a**i−1ora**i, c_i = a_{i-1} + a_{i}c**i=a**i−1+a**i and each a_ia**i is a non-negative integer.
Now, Toilet-Ares asks you to calculate the number of beautiful sequences.
输入描述:
The first line contains one integer nn (2 \leq n \leq 10^5)(2≤n≤105) - the length of sequence aa.
The second line contains n-1n−1 integers b_2,b_3,\ldots,b_nb2,b3,…,bn (0 \leq b_i < 2^{30})(0≤bi<230) - the elements of sequence bb.
The third line contains n-1n−1 integers c_2,c_3,\ldots,c_nc2,c3,…,cn (0 \leq c_i < 2^{31})(0≤ci<231) - the elements of sequence cc.
输出描述:
Print one number - the number of beautiful sequences.
示例1
输入
4
7 5 5
7 9 5
输出
2
代码与解释
b[ i ] = a[ i ] | a[ i − 1 ]
c[ i ] = a[ i ] + a[ i − 1 ]
给出n个数字作为b数组,n个为c数组,问这样的a数组有多少个
首先,要讲一个定理
a+b == a|b + a&b
a+b == a|b + a&b c[i] = b[i] + a[i-1] & a[i] a[i-1]+a[i]=a[i-1] | a[i] + a[i-1] & a[i] c[i] - b[i] = a[i-1] & a[i]
这样,外面可以得到a&b的数组,外面把它定义为d数组
由于c数组的存在,我们只需要知道第一个数字a[1],其他数字都都知道了,所以我们只需要把a[1]的每一位遍历一遍即可
剩下的看代码吧
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <string>
#include <iostream>
#include <sstream>
#include <set>
#include <map>
#include <queue>
#include <bitset>
#include <vector>
#include <limits.h>
#include <assert.h>
#include <functional>
#include <numeric>
#include <ctime>
//#include <ext/pb_ds/assoc_container.hpp>
//#include <ext/pb_ds/tree_policy.hpp>
#define pb push_back
#define ppb pop_back
#define lbnd lower_bound
#define ubnd upper_bound
#define endl '\n'
#define mll map<ll,ll>
#define msl map<string,ll>
#define mls map<ll, string>
#define rep(i,a,b) for(ll i=a;i<b;i++)
#define repr(i,a,b) for(ll i=b-1;i>=a;i--)
#define trav(a, x) for(auto& a : x)
#define pll pair<ll,ll>
#define vl vector<ll>
#define vll vector<pair<ll, ll>>
#define vs vector<string>
#define all(a) (a).begin(),(a).end()
#define F first
#define S second
#define sz(x) (ll)x.size()
#define hell 1000000007
#define DEBUG cerr<<"/n>>>I'm Here<<</n"<<endl;
#define display(x) trav(a,x) cout<<a<<" ";cout<<endl;
#define what_is(x) cerr << #x << " is " << x << endl;
#define ini(a) memset(a,0,sizeof(a))
#define ini2(a,b) memset(a,b,sizeof(a))
#define rep(i,a,b) for(int i=a;i<=b;i++)
#define case ll T;cin>>T;for(ll Q=1;Q<=T;Q++)
#define lowbit(x) x&(-x)
#define pr printf
#define sc scanf
#define _ 0
#define ordered_set tree<ll, null_type,less<ll>, rb_tree_tag,tree_order_statistics_node_update>
#define FAST ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define DBG(x) \
(void)(cout << "L" << __LINE__ \
<< ": " << #x << " = " << (x) << '\n')
#define TIE \
cin.tie(0);cout.tie(0);\
ios::sync_with_stdio(false);
//#define long long int
//using namespace __gnu_pbds;
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int INF = 0x3f3f3f3f;
const ll LLINF = 0x3f3f3f3f3f3f3f3f;
const int maxn = 1e5+10;
const ll N = 5;
ll n, ans = 1, b[maxn], c[maxn], d[maxn];
int check(int w, int x) {
int OR, AND;
for (int i=2; i<=n; i++) {
OR = (b[i]>>w) & 1;//or的第w+1位(因为w开始是0),AND同理
AND = (d[i]>>w) & 1;
if (OR && !AND) x^=1;//如果是奇数^=1就是-1,如果是偶数^=1就是+1,相当于最后一位的取反,其他位不变
else if (!OR && AND) return 0;
else if (!OR && !AND && x==1) return 0;
else if (OR && AND && x==0) return 0;
//解释一下以上四行if else (如果还不懂自己个表格看一看)
//如果OR=1,AND=0,那么有两种可能,0和1
//如果OR=0,AND=1,那么完全不可能出现
//如果OR=0,AND=0,那么只可能x只能是0
//如果OR=1,AND=1,那么只可能x只能是1
}
return 1;
}
void solve(){
cin>>n;
for (ll i=2; i<=n; i++) cin>>b[i];
for (ll i=2; i<=n; i++) cin>>c[i], d[i] = c[i] - b[i];
for (int i=0; i<32; i++) {//遍历所有位
int a = check(i, 0);//这一位是0的可能
int b = check(i, 1);//这一位是1的可能
if (a && b) ans*=2;//如果都可以那就乘2
else if (!a && !b) {//不行就输出0
cout<<0<<endl;
return ;
}
//其他情况ans不变
}
cout<<ans<<endl;
}
int main()
{
// TIE;
// #ifndef ONLINE_JUDGE
// freopen ("input.txt","r",stdin);
// #else
// #endif
solve();
// case{solve();}
// case{cout<<"Case "<<Q<<":"<<endl;solve();}
return ~~(0^_^0);
}