### PROBLEM LINK:

**Author:** Ke Bi

**Tester:** Antoniuk Vasyl and Misha Chorniy

**Editorialist:** Pushkar Mishra

### DIFFICULTY:

Hard

### PREREQUISITES:

linear recurrence, matrix exponentiation

### PROBLEM:

Given a chocolate of size 2 * 2 * 2 * 2 * n. Find out number of ways of breaking it into 8 n small pieces, each of size 1 * 1 * 1 * 1 * 2.

Print the answer modulo 10^9 + 7.

### EXPLANATION:

**Think about a smaller problem**

Let us first solve version of this problem in lower dimension. Let us fix chocolate size = 2 * n and piece size = 1 * 2.

Let dp[i][mask] denote the number of ways of breaking the chocolate up to coordinate i (in 2nd dimension) and where mask denote the configuration of last row.

Here as a single row will contain 2 elements, so mask will have total (1 << 2) possible values.

We can obtain a recurrence for dp by trying to fill the mask in all possible ways and making transitions to next state.

Now, we can note that dp[i][mask] is dependent on dp[i - 1][mask’]. We can represent this relation by a constant matrix of size 2^2 * 2^2.

So, we can find dp[n][mask = (last row is full)] by matrix exponentiation.

**Extending to higher dimenstion**

Now in case of higher dimension, the mask will be 2^(16) as a row will have dimesion 2 * 2 * 2 * 2.

Also, we can obtain the transitions in the similar way.

Now, the size of matrix will be 2^16 * 2^16 which is too huge to apply the matrix exponentiation algorithm.

We can make a few observations to reduce the number of states.

We note that some of the configurations (masks) of last row are equivalent or some of them are useless (can never lead to a solution).

- Some of them are same w.r.t reflection and rotation.
- If there are a odd number of 1s in the state, the dp value of it must be 0.
- We can color it like chess board.If the number of black cells with 1s is not equal the number of white cell with 1, the dp value of it must be 0.

After these modifications, number of states will reduce dramatically, (around 561, see author’s solution for details of implementation of this).

Now the time complexity will be around 561^3 log(10^9) per test case, which will lead to TLE.

We need to optimize this.

**Linear recurrence**

We can notice that matrix is a constant matrix (independent of input n).

So, we can write a linear recurrence for this in the following way

f[n] = coef[1] f[n - 1] + coef[2] f[n-2] + … + coef[561] f[n - 561].

where each coef[i] is a constant.

**Finding simplest recurrence relation**

Now, if we could find f[n] dependent on last few terms rather than the current (i.e. 561).

So, let us say that we have a sequence of 561 numbers f[1], f[2], f[3], …, f[561].

So, for a given sequence, we need to know the smallest n for which a linear recurrence relation could be obtained.

**A method by gaussian elimination**

Let us say that we have a sequence 1, 2, 3, 11, 18, 53, 105

Now, we want to check whether this sequence is a 2-recursive formula (i.e. f[n] depending on previous 2 values f[n - 1], f[n - 2]).

We take a look at the Determinant

1 2 3

2 3 11

3 11 18

Det[{{1, 2, 3}, {2, 3, 11}, {3, 11, 18}}]

The value of the Determinant is not zero, which means it does not have a 2-recursive formula.

Now, let us check whether this is a 3-recursive formula.

Det[{{1, 2, 3, 11}, {2, 3, 11, 18}, {3, 11, 18, 53}, {11, 18, 53, 105}}]

The Det is 0.

Therefore, this has a 3-recursive formula.

So, in general for checking whether a formula is k recursive,

we need to make a determinant of following kind

f[1] f[2] … f[k]

f[2] … f[k + 1]

f[3] … f[k + 2]

.

.

f[k] … f[k + k - 1]

So, we will need to 2 * k values of function f.

For, our problem we get value that formula is 71-recursive formula.

So, we obtain these coefficients using gaussian elimination method used for calculating the previous determinant.

Now, each test case can be solved in O(71^3 log N) per test case.

We can calculate value of f[1], …, f[71 * 2] using the slow method discovered earlier and use it to calculate the desired coefficients.

**Another solution using Cayley-Hamilton theorem**

Given a recurrence relation of type f[n] = coef[1] f[n - 1] + coef[2] f[n-2] + … + coef[k] f[n - k],

we can find f(n) in O(k^2 log n).

You can see this link for details.