refer modulo multiplicative inverse link
Since the modulo given is prime we can go for fermat’s little theoram.
say our denominator is 4 raised to the power of number of # we encounter in the expression.
let Y be the number of # we encountered in our expression.
let M be the prime modulo provided in the problem
By applying fermat’s little theoram,
INV = ((4^Y)^M-2)%M // Q^-1 % MOD
we can do a fast modular exponentiation for base 4 and power Y*(M-2) modulo M
This is my O(|L|) stack-based C++14 solution that computes the answer without creating the binary tree of the well-formed Boolean expression.
CodeChef: Practical coding for everyone. Time complexity of the algorithm is 16*L . But, why am I not getting an AC for big test cases ?. I got partial score of 30% for the question. I request anyone to tell me why performing recursion sometimes for over n=10^6 takes too much time to get accepted in contests. Thanks in advance !
Is this approach to find probability Right or Wrong?
string l;
cin >> l;
l=infixToPostfix(l);
long double p0=0.25,p1=0.25,pa=0.25,pA=0.25;
long double P0,P1,Pa,PA;
for(int j=0;j<l.length();j++)
{
switch(l[j])
{
case '&' : P0=p0+((0.25)*p1)+((0.5)*pa)+((0.5)*pA);
P1=(0.25)*p1;
Pa=(((0.25)*p1)+((0.5)*pa));
PA=(((0.25)*p1)+((0.5)*pA));
break;
case '|' : P0=(0.25)*p0;
P1=((0.25)*p0)+p1+((0.5)*pa)+((0.5)*pA);
Pa=(((0.25)*p0)+((0.5)*pa));
PA=(((0.25)*p0)+((0.5)*pA));
break;
case '^' : P0=0.25;
P1=0.25;
Pa=0.25;
PA=0.25;
break;
}
p0=P0,p1=P1,pa=Pa,pA=PA;
}you’re welcome buddy
My commented code for the solution.
You need the probabilities in rational form, so that you can find the answer modulo a prime number as required by the problem.
Really nice problem.
My solution differed in three aspects.
1.) Rather than creating the expression tree explicitly, I looped through just to find the root operator for the current expression. This can be done by using a stack and finding the first operator where the stack is empty.
2.) I used a generic function that takes in any boolean operator that operates on two variables, and combine the probabilities based on the operator provided.
3.) Because only the final probability mattered, I computed the inverse of the denominator only at the end.
Here is a link to my solution: REBIT SOLN
I would love to hear feedback/suggestions on how to improve! Thanks
Shouldn’t it also be the sum of all 4 numerators? I didn’t calculate the number of #. Searched for days for error and one day I just replaced the denominator and finally received AC. Where was I wrong?
Please help me out …i dont know where i am getting wrong 
https://www.codechef.com/viewsolution/31870565
Try this
1
((((#|#)&#)|#)^((#^#)|#))
Expected Answer
646324225 833495041 757456897 757456897
One possible problem which I can figure out from your code is your way of calculating probability. Set base case as 1 for each operand rather than 0.25 and calculate probability at end.
Try this
1
((((#|#)&#)|#)^((#^#)|#))
Expected Answer
646324225 833495041 757456897 757456897
Indeed it is the same thing. Look we are calculating probability and the sum of all possible probabilities should be equal to 1. Hence numerator by
the denominator needs to be equal.
Hey can anyone point what mistake is there in my code:
#include<bits/stdc++.h>
#define ll long long int
using namespace std;
ll modInverse(ll a, ll m)
{
ll m0 = m;
ll y = 0, x = 1;
if (m == 1)
return 0;
while (a > 1)
{
ll q = a / m;
ll t = m;
m = a % m, a = t;
t = y;
y = x - q * y;
x = t;
}
if (x < 0)
x += m0;
return x;
}
void bitwise(string s){
ll mod = 998244353;
ll n = s.size();
ll count_0 = 1;
ll count_1 = 1;
ll count_a = 1;
ll count_A = 1;
for(int i = 2 ; i < n ; i += 2){
ll curr_0 = count_0;
ll curr_1 = count_1;
ll curr_a = count_a;
ll curr_A = count_A;
if(s[i-1] == '&'){
count_0 = 4*curr_0 + curr_1 + 2*curr_a + 2*curr_A;
count_1 = curr_1;
count_a = 2*curr_a + curr_1;
count_A = 2*curr_A + curr_1;
}
else if(s[i-1] == '|'){
count_0 = curr_0;
count_1 = 4*curr_1 + curr_0 + 2*curr_a + 2*curr_A;
count_a = 2*curr_a + curr_0;
count_A = 2*curr_A + curr_0;
}
else{
count_0 = curr_0 + curr_1 + curr_a + curr_A;
count_1 = curr_0 + curr_1 + curr_a + curr_A;
count_a = curr_0 + curr_1 + curr_a + curr_A;
count_A = curr_0 + curr_1 + curr_a + curr_A;
}
count_0 = count_0 % mod;
count_1 = count_1 % mod;
count_a = count_a % mod;
count_A = count_A % mod;
}
ll total = (count_0 + count_1)%mod;
total = (total + count_a)%mod;
total = (total + count_A)%mod;
total = total%mod;
total = modInverse(total, mod);
ll ans1 = ((count_0%mod)*total)%mod;
ll ans2 = ((count_1%mod)*total)%mod;
ll ans3 = ((count_a%mod)*total)%mod;
ll ans4 = ((count_A%mod)*total)%mod;
cout << ans1 << " " << ans2 << " " << ans3 << " " << ans4 << endl;
}
int main() {
// your code goes here
int t;
cin >> t;
while(t–){
string l;
cin >> l;
string s;
int n = l.size();
for(int i = 0 ; i < n ; i++){
if(l[i] != ‘(’ && l[i] !=’)’)
s.push_back(l[i]);
}
bitwise(s);
}
return 0;
}
This is wrong. I was making similar mistake but then I found out that I was wrong. See my wrong code and correct code.
Thanks a lot for pointing out the mistake.
Could you please elaborate a bit about this.If all of them is set to 1 then how we will calculate the probability.Moreover the denominator will be different for different expression
Mentioned as “Your output” is correct, I checked acroos correct solutions.
Yeah True
Denominator will be sum of all the 4 calculated possibilities . Then you can just multiply every possibility with modulo inverse of Denominator to get answer.