Days of Floral Colours
Contest: Codeforces Round 431 (Div. 1)
Difficulty rating: 3400
Tags: combinatorics, divide and conquer, dp, fft, math

The Floral Clock has been standing by the side of Mirror Lake for years. Though unable to keep time, it reminds people of the passage of time and the good old days.

On the rim of the Floral Clock are 2n flowers, numbered from 1 to 2n clockwise, each of which has a colour among all n possible ones. For each colour, there are exactly two flowers with it, the distance between which either is less than or equal to 2, or equals n. Additionally, if flowers u and v are of the same colour, then flowers opposite to u and opposite to v should be of the same colour as well — symmetry is beautiful!

Formally, the distance between two flowers is 1 plus the number of flowers on the minor arc (or semicircle) between them. Below is a possible arrangement with n = 6 that cover all possibilities.

The beauty of an arrangement is defined to be the product of the lengths of flower segments separated by all opposite flowers of the same colour. In other words, in order to compute the beauty, we remove from the circle all flowers that have the same colour as flowers opposite to them. Then, the beauty is the product of lengths of all remaining segments. Note that we include segments of length 0 in this product. If there are no flowers that have the same colour as flower opposite to them, the beauty equals 0. For instance, the beauty of the above arrangement equals 1 × 3 × 1 × 3 = 9 — the segments are {2}, {4, 5, 6}, {8} and {10, 11, 12}.

While keeping the constraints satisfied, there may be lots of different arrangements. Find out the sum of beauty over all possible arrangements, modulo 998 244 353. Two arrangements are considered different, if a pair (u, v) (1 ≤ u, v ≤ 2n) exists such that flowers u and v are of the same colour in one of them, but not in the other.

Input format:
The first and only line of input contains a lonely positive integer n (3 ≤ n ≤ 50 000) — the number of colours present on the Floral Clock.

Output format:
Output one integer — the sum of beauty over all possible arrangements of flowers, modulo 998 244 353.

Constraints:
Time limit: 7.0 s
Memory limit: 256.0 MB

Note:
With n = 3, the following six arrangements each have a beauty of 2 × 2 = 4.

While many others, such as the left one in the figure below, have a beauty of 0. The right one is invalid, since it's asymmetric.

Example input:
3

Example output:
24

Example input:
4

Example output:
4

Editorial:
tl;dr Just look at recurrences of g, f0, f1 and f2 and the part after f2's recurrence.
Break the circle down into semicircles.
We're basically pairing flowers under the restrictions. It's hard to deal with the whole circle, let's consider something simpler. Consider an arc of length i (segment of i flowers) and their opposite counterparts, surrounded by another two pairs of opposite flowers of the same colour. We will calculate their contribution to the total beauty, f0(i) — in other words, the total beauty if only this segment is required to be coloured (we will not pair them with flowers out of this segment).
We come up with a function g(i), denoting the number of ways to colour a segment of length i with pairs of opposite 1 and 2 only. The recurrence is g(0) = 1, g(1) = 0, g(i) = g(i - 2) + g(i - 4).
First case: there are no opposite pairs within this segment. There are g(i) ways to do this, giving a total beauty of g(i)·i2.
Second case: there is at least one opposite pair within this segment. Fix the position of the first opposite pair, j (in the range of 0 and i - 1 inclusive). Another two cases diverge.
• (a) No pair of distance 2 crosses the flowers at position j. In this case, a subproblem of length i - j - 1 emerge, generating a total beauty of g(j)·j2 × f0(i - j - 1).
• (b) A pair of distance 2 crosses the flowers at position j. In this case, new subproblems appear — an arc of length i - j - 2 and their opposite counterparts, surrounded by an opposite same-colour pair on one side, and an already-paired flower and an opposite same-colour pair on the other. Denote this subproblem as f1, this case generates a total beauty of g(j - 1)·j2 × f1(i - j - 3).
Summing up and simplifying a bit, we get the recurrence for f0:
Doing almost the same (fix the opposite pair nearest to the side of an already-paired flower), we get the recurrence for f1:
Now we've solved the subproblem for a subsegment. Hooray!
For the whole circle, let's fix a pair of opposite flowers. Let it be flowers 1 and n. This can be rotated to generate other arrangements.
But we don't know how many times it can be rotated without duplication. So we fix the second opposite pair, letting it be the first one starting from flower number 2 and going clockwise. Let its position be i, then there shouldn't be any opposite pairs within [2, i - 1], and all arrangements can be rotated in j - 1 different ways to generate all different arrangements.
There may be or may be not pairs of distance 2 crossing over flowers 1 and i. Consider all four cases, we run into another subproblem with déjà vu.
We introduce a new function, f2(i), denoting the total beauty of a segment of length i, with an already-paired flower and an opposite same-colour pair on both sides.
Following the method above, we get
Then the answer can be calculated in linear time, with g, f0, f1 and f2 all calculated beforehand. Overall complexity is O(n2). Refer to the square-time solution below for an implementation.
Then, note that recurrences of f0, f1 and f2 are in the form of convolutions, so we'd like to optimize it with FFT. However, they include convolutions of the previous parts of the function itself, with another function like g(i)·i2, g(i)·(i + 1)2 or g(i)·(i + 2)2.
Under this situation, apply FFT in a divide-and-conquer subroutine. solve(L, R) assumes that f(1;L - 1) are already calculated, and all the terms that contribute to f(L;R) and involve f(1;L - 1) are already accumulated in their corresponding array positions. It finishes calculation of f(L;R). First, it calls solve(L, M), then add all terms that contribute to f(M + 1;R) involving f(L;M) by convolving f(L;M) with the other function (say g(i) × i2), then call solve(M+1, R). Over complexity is $${\mathcal {O}}(n\log ^{2}n)$$.
The model solution solves f0 and f1 in one pass, and f2 in another. They can also be merged into a single pass. Big thanks to you for patiently reading till this point, and if you just want to enjoy the problem rather than implementation, feel free just to write a O(n2) solution :)