PROBLEM LINK:
Author: Devendra Agarwal
Tester: Surya Kiran
Editorialist: Amit Pandey
DIFFICULTY:
Medium-Hard
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(Length-1,\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.. M-1 {
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 