C2381 - Bus Stops

Subtask 2 (80%)

Prefix sum.

C2382 - Roblox Password

Subtask 1 (25%)

DFS will suffice.

Subtask 2 (25%)

Compute $26^N$ mod $10^9 + 7$.

Subtask 3 (50%)

Let $dp[i][j]$ be the number of strings of length $i$ and ending with character $j$, for $i$ from 1 to n and $j$ from a to z. $$dp[i][j] = \begin{cases} 1 & \text{if } i = 1 \\ \displaystyle\sum_{k = a, \cdots, z \text{ where } kj \text{ is not banned}} dp[i - 1][k] & \text{if } i > 1 \end{cases}$$ Remember to modulo $10^9 + 7$ at last.

C2383 - Haha Funny Task

Jono's favorite 2-digit and 3-digit numbers $A$ and $B$ can be found in the time and memory limit.

Let the base be $X = \underbrace{\overline{AA \cdots A}}_{N \text{ times}}$ and the exponent be $Y = \underbrace{\overline{ABAB \cdots AB}}_{N \text{ times}}$. Also let $M = 10^9 + 7$ (note that this is prime).

First, computing $X^Y \mod M$ is equivalent to $(X \mod M)^Y \mod M$ (consider modular arithmetic rules for multiplication).

Also, recall by Fermat's Little Theorem that for an integer $a$ and prime number $p$: $$a^{p - 1} \equiv 1 \pmod{p}$$ Then, for integers $b$ and $c$: $$a^{b(p - 1) + c} \equiv a^c \pmod{p}$$ which means we are interested in the exponent modulo $M - 1$, i.e. the result $(X \mod M)^{Y \mod (M - 1)} \mod M$.

We can compute $X \mod M$ as follows. Initialize the result to zero, then repeat $N$ times: multiply the result by $10^2$ (since $A$ has two digits), add $A$ to the result then modulo $M$. We can compute $Y \mod (M - 1)$ similarly.

Finally, we can compute the answer using binary exponentiation.