### PROBLEM LINK:

**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}**.

**can also be computed in**

^{K}P_{N}**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.