PROBLEM LINK:Author: Devendra Agarwal DIFFICULTY:MediumHard Problem:You are given an array A consisting of prime numbers greater than 4. Fun(S) = $A[S[1]]^{A[S[2]]^{...A[S[N]]}}$ You need to find the sum of the values returned by Fun(S) for every distinct sequence S. Each element of S is an integer from 1 to N. Thus, there are $N^N$ possible sequences in all. As the values can be large, return it modulo M. Solution:Let us first solve a different problem to solve this problem Problem Version 1 :$A_i$ is a prime number greater than $M$ and $N <=1000$ Solution:We will use recursive approach to solve this version of the problem. First notice that $\phi(M)$ or $\phi(....\phi(M))))..)$ will always be coprime to all the numbers. Recursive(L,M) returns an array where array[i] denotes denotes number of times i(less than M) appeared by using all N numbers for tower of length L. You can find Recursive(Length1,$\phi(Modulo)$) and find how many times value v ( which is less than $\phi(modulo)$ ) appeared . You can use this info to calculate Recursive ( Length,Modulo) How ? For every possible v, we will apply on all $A_i$ as the base and calculate the modulo value again and update the counter of how many times the new value appeared. Here is the psedo code for the idea: for all possible v: for all i = 1 .. N: new_val = (A_i^v)%Modulo Times_Now[new_val] = Times_Now[new_val] + Times_Previous[v] Complexity : $Modulo*N*Height$ = $N*M*log(M)$ Base Case : Modulo is 2 or 1 ( which ever is comfortable to you ) Or Length is 1. Problem Version 2 :Little Larger N (~ 1e5 ) and same as version 1. Solution:Now you can use this fact that atmost Modulo different values will be used. Hence you can contract N values into M values and each appearing more than once. for all i = 1..N: Number_of_times_appeared[A_i%Modulo] ++; So, the Loop here changes to : for all possible v { for all i = 0.. M1 { new_val = (i^v)%Modulo Times_Now[new_val]=Times_Now[new_val]+Times_Previous[v]*Number_of_times_appeared[i] } } Time Complexity : $N*height + M*M*height = N*log(M) + M*M*log(M)$ Problem Version 3(Final Version):Now the original problem Solution:Only thing which made our life simpler was that the $A_i$ was coprime to all the modulos in chain. Now, we need to notice some interesting things here: All $A_i$'s are prime numbers greater than 4 => $A_i ^ { any tower }$ % M where $A_i$ is not coprime to M then M must be of the form $p^e * M_2$ , and $A_i$ must be $p$ Now notice that maximum value of e can be 5 for any p ( because $A_i$ > 4 , so smallest p is 5 and $5^6$ is more than 5000 ) Now if we use CRT and break the modulo in these two parts then one part is always 0. (which part ? ) Modulo of the tower from $p^e$ is always 0.(Except the Base Case which can be handled trivially) Reason: Minimum number on the power will be 5, hence modulo with $p^e$ will always fetch 0 as result. Now If we go back to CRT basics, we know that $a^b$ % M can be broken into $R_1 = a^b % M_1$ and $R_2 =a^b % M_2$ Here in our problem a is a prime number, $M_1$ is $a^e$ so, the solution from CRT is : $R_1*M_2*X_1 + R_2*M_1*X_2$ Here $X_1 = Inverse(M_2,M_1) , X_2 = Inverse(M_1,M_2)$ This equation reduces to : $R_2*M_1*X_2$ ( Because $R_1$ is $0$ ) Now this equation says $( a^b \bmod M_2 * M_1 *X_2 ) \bmod M$ is our final solution. Note that $M_1*X_2$ is independent of $A_i$(or the a). Now, the result $( (a^b \bmod M_2) * M_1 *X_2 )\bmod M$ is equivalent to saying $( (a \bmod M_2)*M1*X2 )^b \bmod M$ Reason for the second Part : Take Modulo $M_1$ , you will get $0$ , take modulo $M_2$ , you will get $(a^b) \bmod M_2$. This is the modulo pairs for the $M_1,M_2$ and by uniqueness of solution of crt , this solution is also correct Now whats the benefit from this representation ? We can contract our input which are not coprime by this formula : $(a \bmod M_2)*M_1*X_2$ and rest goes as it was in version 2 :) AUTHOR'S, TESTER'S SOLUTIONS:
This question is marked "community wiki".
asked 30 Jun '15, 16:06

You forgot to write prerequisites, can you please do it now? answered 21 Jul '15, 21:18

@saurv4u.: The prerequisites are 1. Euler's phi function. 2. Number theory 3. exponentiation And you can have a look at this answer.. Stackoverflow question answered 23 Jul '15, 07:48
