# PROBLEM LINK:

Practice

Contest

**Editorialist:** Suhash Venkatesh

# DIFFICULTY:

HARD

# PREREQUISITES:

DP, Math

# PROBLEM:

Given a **2 x N** grid, you have to fill it with numbers from the range **[1..K]** such that there are no **one** or **two** cycles. Find the number of ways in which this can be done.

1 ≤ **N** ≤ 10^{5}

0 ≤ **K** ≤ 10^{18}

# EXPLANATION:

**Simpler version**:

Find the number of derangements of **[1..N]** such that there are no **one** or **two** cycles.

This is equivalent to the initial problem if **N == K**. This can be solved easily using the following recurrence:

`f(n) = (n-1) * f(n-1) + (n-1) * (n-2) * f(n-3)`

, where **f(1) = 0, f(2) = 0, f(3) = 2**.

It can be found on OEIS too, A038205. This can be derived using a similar derivation to number of derangements of **N** numbers. But sadly, this doesn't help much for the harder version of the problem **(K > N)**.

**Actual version**:

It is clear that if **K < N**, then the answer is 0. Hence, going forward we can assume that **K >= N**. For the first row of the grid, we can choose any **N** numbers from the given **K** numbers, and permute them in **N** factorial ways. Hence, number of ways = ^{K}C_{N} * N! = ^{K}P_{N}.

Here, ^{K}C_{N} = K! / [N! * (K-N)!] and ^{K}P_{N} = K! / (K-N)!

From now on, we can assume that the first row is filled with numbers **[1..N]** in order, from left to right (We can multiply the final answer by ^{K}P_{N}). Now, we have to fill the second row with no.s **[1..K]**, such that no **one** or **two** cycles are formed. Let's divide **[1..K]** into 2 buckets:

**Bucket 1**: Contains no.s **[1..N]** => N numbers.

**Bucket 2**: Contains no.s **[N+1..K]** => (K-N) numbers.

*An important property of bucket 2 is that, none of the no.s in this bucket will ever create a cycle.* Let's first try to fill slot 1 (Assume slots are numbered with **[1..N]** from left to right). We can either fill it with a no. from bucket 1 (or) a no. from bucket 2. If we choose a number from bucket 2, let's say N+*i* (1 ≤ *i* ≤ K-N), then we know that the number 1 can occur at any slot since it will never create a cycle. We'll end up with **1 => N+*i***, and any of the slots **[2..N]** can now have the number **1**, without creating any cycle.

**Key Observation**:

*Note that the size of bucket 2 never changes, and is always = (K-N).* In the above description, we can re-label the number 1 as N+*i* and push it into bucket 2. Hence, even after this step - bucket 2 will contain exactly (K-N) no.s. We haven't covered the case where we choose a no. from bucket 1. This is not important right now, since this would anyways not change the size of bucket 2.

**An O(N**^{2}) solution:

Let **f(i)** denote the no. of ways of filling slots [1..i] with no.s from the following 2 buckets: Bucket 1 - **[1..i]** (i numbers), Bucket 2 - **(K-N)** numbers (all these no.s are > i), such that no **one** or **two** cycles are formed. Clearly, **f(N)** is the desired answer.

Let's try to fill slot 1. There are 2 possibilities:

**1.) Pick a number from bucket 1:**

Let's say a_{1} [1 => a_{1}] (means slot 1 is filled with no. a_{1}). Let's try all cycle lengths >= 3: For cycle length = 'j', we'll choose 'j' numbers {1, a_{1}, a_{2}, ..., a_{(j-1)}} such that (**1 <= a**_{m} <= i), and built a 'j' cycle in the following way: [1 => a_{1}, a_{1} => a_{2}, a_{2} => a_{3}, ..., a_{(j-2)} => a_{(j-1)}, a_{(j-1)} => 1].

For a 'j' cycle, the no. of ways = ^{(i-1)}C_{(j-1)} * (j-1)! * f(i-j) = ^{(i-1)}P_{(j-1)} * f(i-j)

Hence, summing over j = 3..i, no. of ways = sum_{(j = 3 to i)} ^{(i-1)}P_{(j-1)} * f(i-j)

After simplification, no. of ways = **(i-1)!** * sum_{(j = 3 to i)} **f(i-j) / (i-j)!**

**2.) Pick a number from bucket 2:**

Let's say we pick the number 'b' from bucket 2. We can do this in **(K-N)** ways. Let's now try all cycle lengths >= 1: For cycle length = 'j', we'll choose 'j' numbers {1, a_{1}, a_{2}, ..., a_{(j-1)}} such that (**1 <= a**_{m} <= i), and built a 'j' cycle in the following way: [1 => a_{1}, a_{1} => a_{2}, a_{2} => a_{3}, ..., a_{(j-2)} => a_{(j-1)}, a_{(j-1)} => 1]. Now, break the cycle by putting the number 'b' in slot a_{(j-1)} [a_{(j-1)} => b].
For a 'j' cycle, the no. of ways = **(K-N)** * ^{(i-1)}P_{(j-1)} * f(i-j)

Hence, summing over j = 1..i, no. of ways = **(K-N)** * sum_{(j = 1 to i)} ^{(i-1)}P_{(j-1)} * f(i-j)

After simplification, no. of ways = **(K-N) * (i-1)!** * sum_{(j = 1 to i)} **f(i-j) / (i-j)!**

Summing both the cases, we have:

**f(i) = (K-N) * f(i-1) + (K-N) * (i-1) * f(i-2) + (K-N+1) * (i-1)!** * sum_{(j = 3 to i)} **f(i-j) / (i-j)!**

**An O(N) solution:**

The constraints don't allow an **O(N**^{2}) solution to pass. We need to do better. By observing the above formula carefully, it can be reduced to **O(N)**.

Let's define **g(i)** = sum _{(j = 1 to i)} **f(j) / j!**

It can be written as **g(i)** = **g(i-1) + f(i) / i!**

And f(i) can be re-written as, **f(i) = (K-N) * f(i-1) + (K-N) * (i-1) * f(i-2) + (K-N+1) * (i-1)! * g(i-3)**

Thus, **f(N)** can be computed in **O(N)**. The final answer is **f(N) * **^{K}P_{N}.

^{K}P_{N} can also be computed in **O(N)**. Hence, the overall complexity of the solution is **O(N)**.

**Note**: '**K**' can be as large as 10^{18}. Be careful with overflows.

# AUTHOR'S AND TESTER'S SOLUTIONS:

Author's solution can be found here.