Edit : $$$I$$$ $$$have$$$ $$$solved$$$ $$$it$$$ $$$now$$$
This problem is from a coding test/contest on Hackerearth which is over now .
I will be asking a subtask of the original problem as I can solve the original problem if I can solve this subtask .
We are given three integers a,b,c .
Constraints : b>0 , b,a <998244353
c<=10^18
Consider an array of size 'c' .
It only consists of only zeroes and ones .
Calculate the probability that the xor of this array is "1" .
Probability of any array element to be zero , is given by a/b .
Example :
c=2
a=1
b=3
(p1=a/b)
Only the following arrays can make xor = 1 ,
1) {0,1} , (probability1) : (1/3)*(2/3) = (2/9)
2) {1,0) , (probability2) : (2/3)*(1/3) = (2/9)
Final answer : 2/9 + 2/9 = 4/9
Answer to be calculated modulo the prime number , 998244353
Thankyou community of codeforces , I finally solved it!
I solved it by finding the recurrence relation , say , a(n) is the probability, that sequence of length n has xor equal to 1 .
Then , $$$a(n)=a(n−1)∗c+z $$$, where $$$c=2∗p1−1$$$ , $$$z=1-p1$$$
Closed form for this can be found here : https://www.wolframalpha.com/input/?i=g%28n%29+%3D+g%28n-1%29*c++%2B+z+
You could just solve this with matrix expo. To give you a hint, let $$$dp[i][j]$$$ be the answer for an array of length $$$i$$$ with an xor of $$$j$$$. See if you can turn this into an $$$O(1)$$$ space dp, and from there apply matrix expo (both of these concepts are described in detail in the tutorial).
Thanks , I solved it by finding the recurrence relation , say , a(n) is the probability, that sequence of length n has xor equal to 1 .
Then , $$$a(n) = a(n-1)*c + z$$$ , where $$$c = 2*p1 - 1$$$ , $$$z = 1-p1$$$
Closed form for this can be found here : https://www.wolframalpha.com/input/?i=g%28n%29+%3D+g%28n-1%29*c++%2B+z+
Hurray!