×

# SEQTOWER - Editorial

Author: Devendra Agarwal
Tester: Surya Kiran
Editorialist: Amit Pandey

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 :)

# AUTHOR'S, TESTER'S SOLUTIONS:

This question is marked "community wiki".

2.5k53137170
accept rate: 20%

19.8k350498541

 0 what is phi here..? answered 20 Jul '15, 15:22 16 accept rate: 33%
 0 You forgot to write prerequisites, can you please do it now? answered 21 Jul '15, 21:18 5★saurv4u 31●2 accept rate: 0%
 0 @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 0★a____ 79●11 accept rate: 20%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×1,250
×1,186
×48
×1

question asked: 30 Jun '15, 16:06

question was seen: 2,288 times

last updated: 09 Feb '16, 19:31