### Pow Pow - SPOJ Posted on May 29, 2015

Overview: The problem asks us to calculate the following expression: $a^{exp^b} \pmod m$ where $0 \le a,b \le 10^5$, $exp = \sum_{i=0}^n \binom{n}{i}^2$, $0 \le n \le 10^5$ and $m = 10^9 + 7$. The three integers $a,b,n$ are given as input.

A naive solution is clearly infeasible, so in order to make the problem simpler we need to think about how to manage the sum of squares of the binomial coefficients. Doing a couple of modifications to $exp$ we can get:

Now, we can give a meaning to this last expression as “the sum of the number of ways to have $i$ elements from a first group of $n$ elements and to have $n-i$ elements from a second group of $n$ elements”. Interestingly, this is equal to “choose $n$ elements from a group of $2n$ elements”. So we reduced $exp$ to be equal to $\binom{2n}{n}$. At this point the problem is not solved yet, we need a couple of additional insights.

So far what we have to calculate has reduced to $a^{\binom{2n}{n}^b} \pmod m$, here we need to realize that $m$ is prime and therefore we can make use of Fermat’s little theorem to get the answer. Applying Fermat’s little theorem will result in calculating $a^E \pmod m$ where:

To calculate $E$ we might want to use Fermat’s theorem again; however, $m-1$ is no longer a prime number.

### Codeforces Round 293 - Problem D Posted on March 12, 2015

Overview: There are $$n$$ people waiting in a queue to enter a escalator. At each second the person in front of the queue either enters the escalator with probability $$p$$ or doesn’t move with probability $$1-p$$, making the whole queue wait behind him. The problem asks to find the expected value of the number of people standing on the escalator after $$t$$ seconds. The input consists of a line with three numbers $$n, p, t$$ $$(1 \le n, t \le 2000, 0 \le p \le 1)$$. Numbers $$n$$ and $$t$$ are integers, number $$p$$ is real, given with exactly two digits after the decimal point.
The solution becomes simpler by using the dynamic programming paradigm. The most straightforward random variable to get the answer would be $$\mathrm{X_t} =$$ the number of people in the escalator after t seconds. And the expected value would be $$\mathrm{E[X_{t}]} = \sum_{i=1}^{n}{i*\mathrm{Pr[X_{t}}=i\mathrm{]}}$$. Where $$\mathrm{Pr[X_{t}}=i\mathrm{]}$$ is the probability that $$i$$ people are in the escalator after $$t$$ seconds.
Now to calculate the probability, we need to be careful with the dependency of the $$i^{th}$$ person on the $$(i-1)^{th}$$ person in the queue. However, if we think about it, to reach that state at $$j$$ seconds we have to make it through whatever the states are at $$j-1$$ seconds. And not surprisingly, there are only two possible states at $$j-1$$ seconds. Either there are $$i-1$$ people in the escalator, which is $$\mathrm{Pr[X_{j-1}}=i-1\mathrm{]}$$, or there are already $$i$$ people in the escalator, which is $$\mathrm{Pr[X_{j-1}}=i\mathrm{]}$$.
Combining them we can easily calculate the state where there are $$i$$ people after $$j$$ seconds. If there are $$i-1$$ people at $$j-1$$ seconds, then in the next second, person $$i$$ enters with probability $$p$$. And if there are already $$i$$ people at $$j-1$$ seconds, then in the next second, person $$i+1$$ does not move with probability $$1-p$$. Therefore, we have: