Problem : https://www.codechef.com/CYAU2019/problems/CYAUG01
Problem name : Easy One!
Problem Difficulty : Simple
Contest Code : CYAU2019
Editorial of Easy one!
In question it was defined that we have to work on bitwise operator so we need to convert string in binary form.
We will work on bitwise OR so lets first know about OR table.
0 | 0 = 0
0 | 1 = 1
1 | 0 = 1
1 | 1 = 1
So by this table we now know that there are 3 ways of getting 1.
So we are given a string as input and we have to tell how many such strings exist so that their bitwise OR value is same as given string.
Let’s consider case of B first:
convert this string to binary:
value of “B”= 1
binary = 000001
Let this binary form as input we need to tell how many input exist for this output.
So for getting 0 as output we have only one option taking that bit as 0 in both input string.
For getting 1 as output we have 3 option
first string bit second string bit Output
1 0 1 0 1 1 1 1 1
So now we know that for each bit value 1 we have 3 options.
So number of input string possible for getting that string as output = (power(3,number of set bits) )% mod
For refrence you can see my code:
using namespace std;
#define max1 100005
#define mod 1000000007