PROBLEM LINK:
Practice
Div-2 Contest
Div-1 Contest
Author: Hasin Rayhan Dewan Dhruboo
Tester: Raja Vardhan Reddy
Editorialist: William Lin
DIFFICULTY:
Easy
PREREQUISITES:
Bits, Basic Combinatorics
PROBLEM:
You are given an array B which represents the bitwise-ors of the prefixes of A. Find the number of possible A.
QUICK EXPLANATION:
If there exists an i such that the set bits in B_i is not a subset of the set bits in B_{i+1}, then the answer is 0. Otherwise, let x be the total number of set bits in all elements of B except for the last element. The answer is 2^x.
EXPLANATION:
Notice that B_{i+1}=B_i \bigvee A_{i+1} (we get a prefix of i+1 by adding element i+1 to the prefix of i). If some bit is set in B_i, then it must also be set in B_{i+1} because bits in x can’t be unset by taking the bitwise-or of x and some other value y. So the first thing we check is that the bits which are set in B_i are a subset of the bits which are set in B_{i+1} for all valid i, and if this condition is not true for some i, the answer is 0.
Code for checking subset
x is a subset of y is equivalent to the condition (x&y)==x (this is a well-known bit trick).
Assume that B_0=0 (this makes sense since the empty prefix should have a bitwise-or value equal to the identity of the operation bitwise-or, which is 0).
For all valid i, we need to make sure that B_{i+1}=B_i \bigvee A_{i+1}. Let’s split the bits into three types:
- The bit is not set in both B_i and B_{i+1}.
- The bit is not set in B_i but it is set in B_{i+1}.
- The bit is set in both B_i and B_{i+1}.
Note that there isn’t a fourth case, otherwise the set bits of B_i would not be a subset of the set bits of B_{i+1}.
For a bit of type 1, the bit in A_{i+1} can only be 0. If it is 1, the bit would be 1 in B_{i+1}.
For a bit of type 2, the bit in A_{i+1} can only be 1. If it is 0, the bit would be 0 in B_{i+1}.
For a bit of type 3, the bit in A_{i+1} can be anything.
Let x be the total number of bits of type 3 over all pairs (B_i, B_{i+1}). Since we have 2 choices for each bit, the answer will be 2^x. It remains to find x.
We can find x simply by iterating over each pair (B_i, B_{i+1}) and counting the bits of type 3. However, there is a more elegant solution.
A bit p will appear in B_i for all i in the range [l, N]. The total count of bits in this range is N-l+1. However, only the bits in range [l+1, N] will be of type 3, so we need to subtract 1 for each bit p. Summing up over each bit p, x is the total count of bits in all elements of B subtracted by the number of bits p which ever appear in the elements of B. If a bit appears in B, it must also appear in the last element of B, so the number of bits p which ever appear in the elements of B is equivalent to the number of bits in the last element of B. Thus, x is the total number of bits in B except for the last element.
SOLUTIONS:
Setter's Solution
#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 9;
const int mod = 1e9 + 7;
inline int mul(int a, int b) {return (a * 1LL * b) % mod;}
int ara[maxn];
int bigMod(int n, int k)
{
if(k == 0) return 1;
int val = bigMod(n, k / 2);
val = mul(val, val);
if(k&1) val = mul(val, n);
return val;
}
int main()
{
int t, cs = 1;
cin >> t;
while(t--){
int n;
cin >> n;
int ans = 1;
scanf("%d", &ara[1]);
for(int i = 2; i <= n; i++){
scanf("%d", &ara[i]);
if((ara[i] & ara[i - 1]) != ara[i - 1]) ans = mul(ans, 0);
else ans = mul(ans, bigMod(2, __builtin_popcount(ara[i - 1])));
}
printf("%d\n", ans);
}
return 0;
}
Tester's Solution
//raja1999
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill - cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x) cout<<fixed<<val; // prints x digits after decimal in val
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
//std::ios::sync_with_stdio(false);
int b[51234],c[51234][33];
main(){
std::ios::sync_with_stdio(false); cin.tie(NULL);
int t;
cin>>t;
// t=1;
while(t--){
int n,i,cnt,ans,j,fl=0;
cin>>n;
rep(i,n){
cin>>b[i];
rep(j,31){
c[i][j]=0;
if(b[i]&(1<<j)){
c[i][j]=1;
}
}
}
ans=1;
f(i,1,n){
cnt=0;
rep(j,31){
if(c[i][j]==1&&c[i-1][j]==1){
cnt++;
}
if(c[i-1][j]==1&&c[i][j]==0){
fl=1;
}
}
ans*=(1<<cnt);
ans%=mod;
}
if(fl){
cout<<0<<endl;
}
else{
cout<<ans<<endl;
}
}
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
const int mxN=5e4, M=1e9+7;
int n, b[mxN];
void solve() {
//input
cin >> n;
for(int i=0; i<n; ++i)
cin >> b[i];
//check that b[i] is subset of b[i+1]
for(int i=0; i+1<n; ++i) {
if((b[i]&b[i+1])!=b[i]) {
cout << "0\n";
return;
}
}
//find x
int x=0;
for(int i=0; i<n-1; ++i)
x+=__builtin_popcount(b[i]);
//2^x
int ans=1;
for(int i=0; i<x; ++i)
ans=ans*2%M;
cout << ans << "\n";
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int t;
cin >> t;
while(t--)
solve();
}
Please give me suggestions if anything is unclear so that I can improve. Thanks 