An easy way to compute $\sum a_k^{a-a_k}\bmod K$, where $a=\sum a_k$

Question

I am given programming assignment, and I am asked to fit into time limit of test cases.

But because of this exponentiation, I don't see how.

Since exponentiation is an expensive operation, I want to do it less number of time.

Is there any simplification of this, so that I can do the same operation in less time?

$$\left(a_1^{a_2+a_3+a_4+a_5+\cdots+a_n}+ a_2^{a_1+a_3+a_4+\cdots+a_n)} +\cdots + a_n^{a_1+a_2+a_3+ \cdots +a_n-1} \right) \bmod K = \text{?}$$ $ 1\le a_i \le 4600, 1\le K \le 1200000, 100 \le n \le 3000$

Answer 1

What about evading exponentiation by taking log then it becomes the sum of the powers into the log and then you must antilog and add.

So each term will be the anti log of $ log((a1)^(a2 + ... +an)) = (a2+a3+...+) log(a1)$

Answer 2

Let $s = a_1 + \dots + a_n$.

The sum is $a_1^{s-a_1} + a_2^{s-a_2} + \dots + a_n^{s-a_n} \mod K$

Depending on what values $a_i$ and $K$ take, this may be fast enough to compute with modular exponentiation.

Answer 3

If we call $a_1+a_2+...+_n=a$,

We can rewrite:

$$\displaystyle a_1^ {(a_2+a_3+a_4+a_5+..+a_n)}+ a_2^{(a_1+a_3+a_4+...+a_n)} +...+a_n^{(a_1+a_2+a_3...+a_{n-1})} $$

Like this:

$$\displaystyle \sum_{i=1}^{n} a_i^ {a-a_i} $$

Hence:

$$\displaystyle (\sum_{i=1}^{n} a_i^ {a-a_i}) \mod K \\= \sum_{i=1}^{n} (a_i^ {a-a_i}\mod K)\\= \sum_{i=1}^{n} (a_i \mod K)^ {a-a_i} \mod K$$

In the last expression, you first take $\mod K$ operator and thus the base will be decreased in order to increase calculation speed.