please explain your approach? is there is any formulae?
This problem was from a very old contest, you can see all sorts of solutions here.
In fact, a lot of people copied the same solutions from that contest…
Here’s mine, which takes O(M\times log(N)) in runtime.
My thought process went like this:
First, realize that x^p \equiv (x \bmod M)^p \bmod M.
This reduces \displaystyle\sum_{c=0}^{N} c^c \bmod M for all c > M to a geometric series sum where c < M, essentially:
\displaystyle\sum_{c=0}^{N} c^c \bmod M \equiv \displaystyle\sum_{c=0}^{M-1} \displaystyle\sum_{k=0}^{\lfloor\frac{N-c}{M}\rfloor} c^{c + k M} \bmod M,
Which can be broken down into:
\displaystyle\sum_{c=0}^{M-1} c^c \displaystyle\sum_{k=0}^{\lfloor\frac{N-c}{M}\rfloor} c^{k M} \bmod M,
As fast as that sounds, all that left right now is to calculate the geometric series sum \displaystyle\sum_{k=0}^{\lfloor\frac{N-c}{M}\rfloor} c^{kM} \bmod M, which can be reduced to the geometric series formula. However, because M is not always coprime with the divisor, I cannot use the formula with Modular Multiplicative Inverse and Fermat’s little theorem. I can, however, use matrix exponentiation to calculate the sum:
\begin{pmatrix}c^M & 1 \\ 0 & 1 \end{pmatrix} ^ {\lfloor\frac{N-c}{M}\rfloor} = \begin{pmatrix}c^{M {\lfloor\frac{N-c}{M}\rfloor}} & \displaystyle\sum_{k=0}^{{\lfloor\frac{N-c}{M}\rfloor} - 1} c^{kM} \bmod M \\ 0 & 1 \end{pmatrix}
Adding the 2 components on the first row gives the geometric series sum. This means I can apply fast exponentiation to the matrix exponentiation and that will calculate the sum in O(log(\lfloor\frac{N-c}{M}\rfloor)) time.
In total, I took M-1 iterations of O(log(M) + log(\lfloor\frac{N-c}{M}\rfloor)) to calculate c^c and geometric series sum. And reducing the runtime estimation:
O(log(M) + log(\lfloor\frac{N-c}{M}\rfloor)) = O(log(M) + log(N) - log(M)) = O(log(N)),
Thus my runtime ended at O(M\times log(N)) and I am done.
Quick note that for c = 0 only 0^0 = 1, and all other 0^k = 0, thus our actual answer will be:
\displaystyle\sum_{c=0}^{N} c^c \bmod M \equiv 1 + \displaystyle\sum_{c=1}^{M-1} c^c \displaystyle\sum_{k=0}^{\lfloor\frac{N-c}{M}\rfloor} c^{k M} \bmod M.
For a detailed explanation, read below.
Click to view
Modular Exponentiation Property
First, there’s the basic property in modular arithmetic that:
(a \times b) \bmod M = ((a \bmod M) \times (b \bmod M)) \bmod M
Therefore, for c^c \bmod M, we can write it as:
(c \bmod M) \times (c \bmod M) \times (c\bmod M) \dots multiplied c number of times, thus:
c^c \bmod M = (c \bmod M)^c \bmod M
How is this useful?
Say we’ll take the sum of f(15) = 0^0 + 1^1 + 2^2 + \dots + 15^{15} and our modulo M = 4:
For 6^6 \bmod 4 we can write it as (6 \bmod 4)^6 \bmod 4= 2^6 \bmod 4
similarly, 10^{10} \bmod 4 = (10 \bmod 4)^{10} \bmod 4= 2^{10} \bmod 4
and, 14^{14} \bmod 4 = (14 \bmod 4)^{14} \bmod 4= 2^{14} \bmod 4
Thus, instead of adding 2^2 + 6^6 + 10^{10} + 14^{14} \bmod 4, we can add it as:
2^2 + 2^6 + 2^{10} + 2^{14} \bmod 4
Simplifying it further:
2^2 + 2^6 + 2^{10} + 2^{14} \bmod 4 = 2^2(1 + 2^4 + 2^8 + 2^{12}) \bmod 4
You can see the sum in the parenthesis is a geometric series sum in which the exponent increased by 4 each time, simply because it’s clocked by the modulo 4. Thus, we can calculate our f(15) this way as the numbers are clocked by the modulo 4:
0^0 + 1^1(1 + 1^4 + 1^8 + 1^{12}) + 2^2(1 + 2^4 + 2^8 + 2^{12}) + 3^3(1 + 3^4 + 3^8 + 3^{12}) + 0^4(1 + 0^4 + 0^8) \bmod 4
The zeroes at the end do not factor into our sum, thus we only need to worry about the numbers 0 < c < M. For a general number c and M, change 2^2(1 + 2^4 + 2^8 + 2^{12}) \bmod 4 to:
c^c(c^0 + c^M + c^{2M} + c^{3M} + \dots + c^{\lfloor\frac{N-c}{M}\rfloor M}) \bmod M
Why the floor \lfloor\frac{N-c}{M}\rfloor? Because we took away c from the exponents, we’ll add no numbers greater than N^N, and the exponents are clocked by modulo M. In standard math notation then:
c^c \displaystyle\sum_{k=0}^{\lfloor\frac{N-c}{M}\rfloor} c^{k M} \bmod M
And because we need to do this for all c that 0 < c < M, our sum f(N) can be written as:
\displaystyle\sum_{c=1}^{M-1} c^c \displaystyle\sum_{k=0}^{\lfloor\frac{N-c}{M}\rfloor} c^{k M} \bmod M
And we have the only exception 0^0 = 1 here, thus:
f(N) = 1 + \displaystyle\sum_{c=1}^{M-1} c^c \displaystyle\sum_{k=0}^{\lfloor\frac{N-c}{M}\rfloor} c^{k M} \bmod M
Matrix Exponentiation
There’s a geometric series sum formula you can use:
\displaystyle\sum_{k=0}^{\lfloor\frac{N-c}{M}\rfloor} c^{k M} \bmod M = \frac{1 - c^{(\lfloor\frac{N-c}{M}\rfloor + 1)M}}{1 - c^M} \bmod M \equiv \frac{c^{(\lfloor\frac{N-c}{M}\rfloor + 1)M} - 1}{c^M - 1} \bmod M, where c^M \neq 1
But consider when c = 3 and M = 4, our divisor equals 80 and is not coprime with M = 4, thus our modular multiplicative inverse for this sum is undefined, and we cannot use Fermat’s little theorem either. Also, who wants to deal with the case when 1^M = 1? Thus, we’ll move on to Matrix Exponentiation.
I’m not super well versed in this and I’ve never learned linear algebra, but I’ll show my thought process. Start out by trying recurrences of geometric sum, for example, some number c in f(N) = c^0 + c^1 + c^2 + \dots + c^{N-1} where N > 1, say our base case f(1) = c^0 = 1, it’s easy to see that:
f(N) = c^{N-1} + f(N-1)
Wouldn’t it be nice if we can factor out more of the geometric series sum? Turns out, we can also write the recurrence this way:
Where N = a + b, and a \geq 1, b \geq 1:
f(N) = c^{a}f(b) + f(a)
So from recurrence, we can build the matrix recurrence:
\begin{pmatrix}c^a & 1 \\ \dots & \dots \end{pmatrix} \times \begin{pmatrix}f(b) \\ f(a)\end{pmatrix} = \begin{pmatrix}f(N) \\ \dots \end{pmatrix}
Keeping f(a) constant such that we can apply matrix exponentiation:
\begin{pmatrix}c^a & 1 \\ 0 & 1 \end{pmatrix} \times \begin{pmatrix}f(b) \\ f(a)\end{pmatrix} = \begin{pmatrix}f(N) \\ f(a) \end{pmatrix}
Then for any N, we can exponent the first matrix by some arbitrary p, such that:
\begin{pmatrix}c^a & 1 \\ 0 & 1 \end{pmatrix}^p \times \begin{pmatrix}f(b) \\ f(a)\end{pmatrix} = \begin{pmatrix}f(N) \\ f(a) \end{pmatrix}
In fact, we can reduce f(b) and f(a) to base case f(1) = 1, such that they’re not even considered in the matrix:
\begin{pmatrix}c & 1 \\ 0 & 1 \end{pmatrix}^p \times \begin{pmatrix}1 \\ 1\end{pmatrix} = \begin{pmatrix}f(2) \\ 1 \end{pmatrix}
This shows that we’re really only concerned with the first matrix, which we can apply matrix exponentiation on:
\begin{pmatrix}c & 1 \\ 0 & 1 \end{pmatrix}^p = \begin{pmatrix}c^p & f(p) \\ 0 & 1 \end{pmatrix}
The sum, \displaystyle\sum_{k=0}^{\lfloor\frac{N-c}{M}\rfloor} c^{k M} \bmod M, can be modeled to this matrix, where c = c^M and p = \lfloor\frac{N-c}{M}\rfloor. A quick remainder that f(N) = c^0 + c^1 + c^2 + \dots + c^{N-1}, our sum is equivalent to c^N + f(N), which can be found in the matrix by adding the two components in the first row below:
\begin{pmatrix}c^M & 1 \\ 0 & 1 \end{pmatrix}^{\lfloor\frac{N-c}{M}\rfloor} = \begin{pmatrix}c^{\lfloor\frac{N-c}{M}\rfloor M} & f({\lfloor\frac{N-c}{M}\rfloor}) \\ 0 & 1 \end{pmatrix}
Fast Modular Exponentiation
Now apply fast modular exponentiation to this matrix exponentiation like you could for a normal integer exponentiation to speed up its runtime from O(\lfloor\frac{N-c}{M}\rfloor) to O(log(\lfloor\frac{N-c}{M}\rfloor)). The general idea of modular exponentiation is to continue squaring a temporary variable and only multiply it with the actual answer when the bits of the exponent at that square corresponds to 1.
For example, consider an exponent of 11:
Instead of doing the normal multiplication:
\begin{pmatrix}c^M & 1 \\ 0 & 1 \end{pmatrix} \times \begin{pmatrix}c^M & 1 \\ 0 & 1 \end{pmatrix} \times \begin{pmatrix}c^M & 1 \\ 0 & 1 \end{pmatrix} \times \dots 11 times
Consider the binary representation of 11: 1011_2
We can write out the multiplication in exponents in the powers of 2 which corresponds to the 1 bits of 11:
\begin{pmatrix}c^M & 1 \\ 0 & 1 \end{pmatrix}^8 \times \begin{pmatrix}c^M & 1 \\ 0 & 1 \end{pmatrix}^2 \times \begin{pmatrix}c^M & 1 \\ 0 & 1 \end{pmatrix}^1
In other words, keep a temporary matrix to be continuously squared, and only multiply it by the answer matrix when the bits of our exponent corresponds to 1.
This completes our runtime to find the geometric series sum. Now what about c^c \bmod M? That’s included in the modular exponentiation for integers so I’m not going to explain. Multiply c^c \bmod M with geometric series sum and we’ll have c^c \displaystyle\sum_{k=0}^{\lfloor\frac{N-c}{M}\rfloor} c^{k M} \bmod M. Do this for all 1 \leq c \leq M-1 and we’d complete our sum, \displaystyle\sum_{c=1}^{M-1} c^c \displaystyle\sum_{k=0}^{\lfloor\frac{N-c}{M}\rfloor} c^{k M} \bmod M.
Add 1 to the final answer for 0^0 and take the \bmod M, and we calculated f(N) \bmod M.
10 Likes
if(m<=n)
e.g : (2^2+(m+2)^(m+2)+(m2+2)^(m2+2)+…)mod(m)=2^2(1+2^m+2^2*m+…) which is a simple sum of GP.Do this for m number therfore O(m).
else
calculate trivialy 1^1+2^2+3^3+… therefore in worst case O(10^3)
You probably know that one can calculate the power of a number in logarithmic time. You can also do so for calculating the sum of the geometric series. Since it holds that1 + a + a^2 + … + a^(2*n+1) = (1 + a) * (1 + (a^2) + (a^2)^2 + … + (a^2)^n), you can recursively calculate the geometric series on the right hand to get the result.
This way you do not need division, so you can take the remainder of the sum (and of intermediate results) modulo any number you want.
algo:- geometricSeriesMod[a_, n_, m_] :=
Module[ {q = a, exp = n, factor = 1, sum = 0, temp},
While[And[exp > 0, q != 0],
If[EvenQ[exp],
temp = Mod[factorPowerMod[q, exp, m], m];
sum = Mod[sum + temp, m];
exp–];
factor = Mod[Mod[1 + q, m]factor, m];
q = Mod[q*q, m];
exp = Floor[ exp /2]; ];
Return [Mod[sum + factor, m]] ] Parameters:
a is the “ratio” of the series. It can be any integer (including zero and negative values).
n is the highest exponent of the series. Allowed are integers >= 0.
m is the integer modulus != 0
the solution provided by 5 star guy @Mr is not the way an actual 2 or 3 star person can understand…its actually a high level…it shud hve broken down in steps in order to understand…just because u understand it doesn"t mean u can put it in same way to different person…basically less than 5 star people needs more explanation to understand the logics…try to provide better explanation dude…no hard feelings…cheers up!
1 Like
@liaojh uses standard mathematical notation and his approach is pretty clear. He has even provided a link to a tutorial for matrix exponentiation, which is the core algorithm he has used. Maybe you should actually put in some effort into understanding the solution.
1 Like
When copying an explanation from elsewhere you should at least give credit to the original writer. (Source)
3 Likes
please explain in easy way for 2-3 star users.huh