Link:https://www.codechef.com/CODN2018/problems/EVNDIL
Can anyone explain the solution for this?
The problem is to find the number of ways we can have an even number of zeros in a string. So for some 2i number of zeroes, 0 \leq i \leq {\dfrac{k}{2}}, the number of possible strings of length k are {k\choose 2i}\cdot 9^{k-2i}, this is k\choose k-2i ways of selecting the positions for the non zero characters, and 9^{k-2i} number of ways we could select these characters.
Now the problem reduces to finding the summation:
\sum_{i = 0}^{\lfloor k/2\rfloor}{k\choose 2i}\cdot 9^{k-2i}
It would take \Omega(k) time to compute, which is infeasible under one second since k can be upto 10^{18}. So this needs to be simplified further which can be done using the binomial expansions of (9 + 1)^k and (9 - 1)^k in the following way:
(9 + 1)^k=\sum_{i = 0}^{k}{k\choose i}\cdot 1^i\cdot 9^{k - i}
(9 - 1)^k=\sum_{i = 0}^{k}{k\choose i}\cdot (-1)^i\cdot 9^{k-i}
\therefore 10^k + 8^k = 2\cdot \sum_{i = 0}^{\lfloor k/2\rfloor}{k\choose 2i}\cdot 9^{k-2i}
($\because$ the odd terms cancel out leaving behind two times every even term)
\implies \sum_{i = 0}^{\lfloor k/2\rfloor}{k\choose 2i}\cdot 9^{k-2i} = \dfrac{10^k + 8^k}{2}
Both 10^k and 8^k could be computed using repeated exponentiation which would take \mathcal{O}(log(k)).
Here’s a simple implementation in C++, and a Python one liner.
2 Likes
first see the constraints
k\leq 10^{18} \text{ & } t\leq 10^4
.
From there the time complexity can’t be anything more than O(\log{k}).
The solution : consider the k digit strings which have x 0’s. You can choose x places for 0’s in kCx ways and other places can be filled by other 9 numbers in 9^{k-x} ways. So no. of ways in which we have x 0’s in k string are kCx*9^{k-x}.
Total no. of k strings having even no. of zeroes are
kC_0*9^k + kC_2*9^{k-2} + kC_4*9^{k-4}+...... = \frac{(9+1)^k + (9-1)^k}{2} = \frac{10^k+8^k}{2}
Now you can find 10^k , 8^k in O(\log{k}) time.
also since 10^9 + 7 is a prime using fermat’s theorem we can find modular inverse of 2 using modular exponentiation as 2^{num-2}\mod{num} where num is 10^9+7.
Here is my submission for your reference.
2 Likes
You can also solve this problem using MATRIX-EXPONENTIATION ! But I have realised that this is an overkill after seeing the solutions of other contestants ! So,what you can do is first find the answer for k=1,k=2,k=3 nd k=4 then using the same technique which we use for finding nth term in fibonacci series you can find the answer for n=k ! My solution : https://www.codechef.com/viewsolution/17865825 !
Hope you like it ! Happy coding !
we don’t even need to find it for k=2,3,4. we know that F(0)=1 , F(1)=9 and the recurrence relation F(n)=18F(n-1)-80F(n-2). that’s it
My idea uses matrix exponentiation, but the solutions mentioned here are much simpler and better 
yeah exactly !
@hemanth_1, I am not able to figure out how you arrived at the recurrence relation (to be used in matrix exponentiation) without knowing that the answer is \frac{10^k+9^k}{2} .Once you know the formula it’s easy to reach F(n)=18F(n-1)-80F(n-2).But how you figured it out without knowing this. Can you please elaborate on it
That was not the recurrence that I got. What I thought was:
Even(i) = Number of strings of length ‘i’ having even number of '0’s.
Odd(i) = Number of strings of length ‘i’ having odd number of '0’s.
Even(i) = 9*Even(i-1) + Odd(i-1)
Odd(i) = 9*odd(i-1) + Even(i-1)
1 Like
why do we went upto k/2 iterations ??
" print(((pow(10, k, 1000000007) + pow(8, k, 1000000007)) * (500000004)) % (1000000007)) " Why it is multiplied by 500000004 ??
@harrypotter0 500000004 is inverse of 2 mod 10^9+7.
Since we have to divide 8^k+10^k by 2 , we multipied by its mod by inverse of 2.
if we divide it by 2 I was getting WA .
yes because (a/b)%mod !=(a%mod / b%mod)
1 Like
yes instead it’s \frac{a}{b} \equiv ab^{-1}\mod{m}, but GCD(b,m) must be equal to 1
okk thanks for your help