0
$\begingroup$

Given an N x M matrix. The task is to repeat the following steps K! times.

  1. Add all the elements of the matrix and get a matrix sum (S) % mod 10^9 + 7
  2. Add S to all the elements. % mod 10^9 + 7
  3. Repeat.

What I can think of regarding the complexity it will O(K! x N x M).

But K ranges from 1 to 10^5 and this is a huge number of iterations for a computer to process.

Is there a way to optimize these operations so that these can be performed using less computational resources.

Thank You.

$\endgroup$
  • $\begingroup$ Do you use any matrix operations or simply have array that stores numbers and happen to be matrix? If this is from some contest please credit the sources. What have you tried so far? $\endgroup$ – Evil Jul 17 '17 at 3:56
  • $\begingroup$ What's the source where you encountered this problem? Can you credit the original source? $\endgroup$ – D.W. Jul 17 '17 at 6:25
1
$\begingroup$

Suppose that the original elements are $a_{ij}^{(1)}$. Their sum is $S^{(1)} = \sum_{ij} a_{ij}^{(1)}$, and the new elements are $a_{ij}^{(2)} = a_{ij}^{(1)} + S^{(1)}$. The new sum is $S^{(2)} = \sum_{ij} a_{ij}^{(1)} + nmS^{(1)} = (1+nm)S^{(1)}$, and the new elements are $a_{ij}^{(3)} = a_{ij}^{(1)} + (2+nm)S^{(1)}$. The new sum is $S^{(3)} = S^{(1)} + nm(2+nm)S^{(1)} = (1+nm)^2S^{(1)}$, and so on.

More generally, you can prove by induction that $S^{(t)} = (1+nm)^{t-1} S^{(1)}$ and $a_{ij}^{(t)} = a_{ij}^{(1)} + \frac{(1+nm)^{t-1}-1}{nm} S^{(1)}$. It remains to find a fast way to calculate expressions such as $S^{(k!)} = (1+nm)^{k!-1} S^{(1)}$ modulo the given prime $p = 10^9 + 7$. You do the rest.

$\endgroup$
  • $\begingroup$ How did you infer the S2 to be sum of all Aij and nmS1 ?? I didn't get that. $\endgroup$ – deadpoolAlready Jul 17 '17 at 13:03
  • $\begingroup$ Take it as an exercise. $\endgroup$ – Yuval Filmus Jul 17 '17 at 13:04
  • $\begingroup$ And can you tell me how to be this smart to figure of this maths so fast? I always struggle with proving by induction, figuring out equations. Any resources you could guide me to. $\endgroup$ – deadpoolAlready Jul 17 '17 at 13:05
  • $\begingroup$ Practice and you will get better. $\endgroup$ – Yuval Filmus Jul 17 '17 at 13:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.