Suppose you haven't labeled any nodes yet. So to label the first node, how many options do you have? $1$.

After labeling that node, its $K$ children will become available as option, but it itself will no longer be an option. So your number of options increases by $K-1$.

This means, you can label first node in $1$ way.
You can label second node in $1 + K-1$ ways.
You can label third node in $1 + K-1 + K-1 = 1 + 2\times(k-1)$ ways.
So you can label $i$-th node in $1 + (i-1)\times(K-1)$ ways.

Thus $F(N,K) = \prod\limits_{i=1}^{N} (1 + (i-1)\times(K-1))$

Subtask 1

Since $N \leq 10^6$, we can just run a loop to find each term of $F(N,K)$ and divide it by $P$ as much as possible to remove all factors of $P$ to find $\frac{F(N,K)}{P^Z}$ where $Z$ is maximum.

One mistake here can be dividing by $P$ after some modulo operation, but that mistake is easy enough to notice as it'd show wrong answer even in sample I/O.

Time Complexity: $O(N\log_P{N})$

Subtask 2

Here $N \leq 10^{12}$, but $K \leq 2$ only. When $K = 1$, answer is always one anyway. When $K=2$, $F(N,K)$ is basically $N!$. But how do you even find $N!$ for such big constraint?

The trick is in the size of $P^Q$. In this subtask $Q = 1$ though, so modulo is effectively by $P$ only, thus the problem converts to finding $N! \pmod{P}$.

Consider $N=10$. Then $N!=1 \times 2 \times 3 \times 4 \times 5 \times 6 \times 7 \times 8 \times 9 \times 10$.

Suppose $P=3$. So after each $P$ terms, the mod value for each term repeats. (It can be proven, that will be left for reader's brainstorming).

i.e. $N!=1 \times 2 \times 0 \times 1 \times 2 \times 0 \times 1 \times 2 \times 0 \times 1 \pmod{P}$.

So you can just find $F(P-1, K)$ using a normal loop like in subtask 1, and then multiply $F(P-1, K)^{N/P}$ to answer due to $F(P-1, K)$ being repeated $N/P$ times. You will then be missing the $(N\mod{P})-1$ terms (the ones after the last multiple of $P$, $10$ in our example), you can easily multiply them to answer by running loop since $(N\mod{P})-1 \leq P$.

But we are still missing some terms. Consider $6$. Dividing it by $P$ leads to $2$. Our answer is missing that. In fact, we are ignoring all multiples of $P$. What are these multiples of $P$ anyway?

$P$, $2P$, $3P$, $4P$, $5P$, $6P$.....

Note that all of these terms have $P$ in common. So what do you get when you divide them all by $P$?

$1$, $2$, $3$, $4$, $5$, $6$..... i.e. multiplicating them results in factorial again!

There will be $N/P$ such terms. So basically you just need to find $F(N/P, K)$ again and multiply it to answer. So the problem converts to a smaller sub-problem. This can be solved both recursively and iteratively. The base case will be when $N < P$, you can find that with a simple loop. The number of levels in recursion will be $\log_P{N}$.

Time Complexity: $O(P\log_P{N})$

Subtask 3

Since $K \leq 10^6$ now, $F(N,K)$ is no longer a simple factorial. Instead, $F(N,K) = \prod\limits_{i=1}^{N} (1 + (i-1)\times(K-1))$

First thing first, what if $P | (K-1)$ i.e. $K-1$ is divisible by $P$?
Then, $1 + (i-1)\times(K-1) \equiv 1 \pmod{P}$, so the answer is always just $1$. So the main concern is when $K-1$ is not divisble by $P$.

Suppose $K = 6$ and $P = 3$.
$F(N,5) = 1 \times 6 \times 11 \times 16 \times 21 \times 26 \times 31 \times 36 \times 41 \times 46 \times 51 \times 56 \times 61 \times 66.....$

What about after taking modulo $P=3$?
$F(N,5) = 1 \times 0 \times 2 \times 1 \times 0 \times 2 \times 1 \times 0 \times 2 \times 1 \times 0 \times 2 \times 1 \times 0..... \pmod{3}$

Do you see that? There are $P$ numbers repeating in this sequence too! But why? Well, it's just some basic modular arithmetic.

What our $i$-th term? $1 + (i-1)\times(K-1)$

When we take it modulo $P$, it becomes $1 + (i-1)\times(K-1) \equiv 1 + ((i-1)\mod{P}\times(K-1) \pmod P$.

So for any $i > P$, the $i$-th term will be equal to a $j$-th term where $j = (i-1)\mod{P}$. And since $P \leq 10^6$, you can find that in a loop like before or just precompute it. For the sake of convenience, we will stick to a solution almost similar to subtask 2.

So, to find $F(N,5)\pmod{P}$, we can run a loop to find the repeating part and then do an exponentiation of it to find its contribution in answer like before. We can also find the the remaining parts at start or at end using loop. But what about the terms divisible by $P$?

In our example, these terms are $6, 21, 36, 51, 66...$

But unlike before, if we dividie these terms by $P=3$, the starting term is not $1$. Instead, they become
$2, 7, 12, 17, 22...$

Note that the difference between them is still the same $K-1 = 5$ (the proof of this is also left to readers as it's not that hard).

So basically, our new sub-problem is like the same problem as before, but with a different starting term. Is that really a problem? Well, it might not be that easy to implement at first, but it's not hard to handle too, since you are running loops in each state anyway.

With a loop, you can easily find the first term divisible by $P$ in any state. You can then divide it by $P$ to find the first term of your next sub-problem. Implementation might be easier if it does done recursively, the starting term and number of terms should be kept as parameter in each state.

Time Complexity: $O(P\log_P{N})$

Subtask 4

Now we have $Q \geq 1$, so some extra things need to be handled.

For starters, if $P | (K-1)$, answer is not simply $1$. But it is still guaranteed that there is still a repeatation after every $P^Q$ terms (not $P$ terms), which can be proven like before. For $P | (K-1)$, it is also guaranteed that no term in $F(N,K)$ is divisible by $P$ (easy to prove). So, you can just find the repetitive part by a loop and find answer like previous approaches.

Whe $K-1$ is not divisible by $P$, some terms may become divisible by $P$ and you need to handle them like before. But note that there is no repetition after $P$ terms, the repetition is after $P^Q$ terms. So we take the part being repeated without the terms divisible by $P$. Then we do exponentiation of it and handle the remaining part like before, to find the contribution of terms not divisible by $P$.

What about the terms divisible by $P$? Well, if we divide them by $P$, we again have the same subproblem as in subtask 3!

Time Complexity: $O(P^Q\log_P{N})$

Statistics

17% Solution Ratio
NirjhorEarliest, Jun '20
NirjhorFastest, 1.7s
NirjhorLightest, 131 kB
NirjhorShortest, 1522B
Toph uses cookies. By continuing you agree to our Cookie Policy.