Triangle Coloring
Contest: Educational Codeforces Round 143 (Rated for Div. 2)
Difficulty rating: 1600
Tags: combinatorics, math

You are given an undirected graph consisting of $$$n$$$ vertices and $$$n$$$ edges, where $$$n$$$ is divisible by $$$6$$$. Each edge has a weight, which is a positive (greater than zero) integer.

The graph has the following structure: it is split into $$$\frac{n}{3}$$$ triples of vertices, the first triple consisting of vertices $$$1, 2, 3$$$, the second triple consisting of vertices $$$4, 5, 6$$$, and so on. Every pair of vertices from the same triple is connected by an edge. There are no edges between vertices from different triples.

You have to paint the vertices of this graph into two colors, red and blue. Each vertex should have exactly one color, there should be exactly $$$\frac{n}{2}$$$ red vertices and $$$\frac{n}{2}$$$ blue vertices. The coloring is called valid if it meets these constraints.

The weight of the coloring is the sum of weights of edges connecting two vertices with different colors.

Let $$$W$$$ be the maximum possible weight of a valid coloring. Calculate the number of valid colorings with weight $$$W$$$, and print it modulo $$$998244353$$$.

Input format:
The first line contains one integer $$$n$$$ ($$$6 \le n \le 3 \cdot 10^5$$$, $$$n$$$ is divisible by $$$6$$$).

The second line contains $$$n$$$ integers $$$w_1, w_2, \dots, w_n$$$ ($$$1 \le w_i \le 1000$$$) — the weights of the edges. Edge $$$1$$$ connects vertices $$$1$$$ and $$$2$$$, edge $$$2$$$ connects vertices $$$1$$$ and $$$3$$$, edge $$$3$$$ connects vertices $$$2$$$ and $$$3$$$, edge $$$4$$$ connects vertices $$$4$$$ and $$$5$$$, edge $$$5$$$ connects vertices $$$4$$$ and $$$6$$$, edge $$$6$$$ connects vertices $$$5$$$ and $$$6$$$, and so on.

Output format:
Print one integer — the number of valid colorings with maximum possible weight, taken modulo $$$998244353$$$.

Constraints:
Time limit: 3.0 s
Memory limit: 512.0 MB

Note:
The following picture describes the graph from the first example test.

The maximum possible weight of a valid coloring of this graph is $$$31$$$.

Example input:
12
1 3 3 7 8 5 2 2 2 2 4 2

Example output:
36

Example input:
6
4 2 6 6 6 4

Example output:
2

Editorial:
Let's ignore the constraint on the number of red/blue vertices for a moment. What is the maximum possible weight of a coloring? From any triple, we can have any two edges connect vertices of different colors. So, the maximum possible weight of a coloring (not necessarily a valid one) is the sum of all edge weights except for the minimum weight in each triple.
Let's show that it is always possible to choose a valid coloring to achieve this weight. In each triple, we should make sure that the two maximum edges connect vertices with different colors; to do this, we can color the vertex incident to both of these edges in one color, and the two other vertices will be painted in the other color. So, for each triple of vertices, there will be either one red vertex and two blue ones, or two red ones and one blue. Let's suppose the first $$$\frac{n}{6}$$$ triples have one red vertex and two blue vertices each, and the other $$$\frac{n}{6}$$$ triples have one blue vertex and two red vertices each. That way, we obtain a valid coloring with maximum possible weight.
Okay, now let's try to find out how do we calculate the number of valid colorings with the maximum possible weight. Each triple of vertices will be either "red" (two red vertices, one blue), or "blue" (the other way around). Since exactly half of the vertices should be red, then exactly half of the triples should be red, so the number of ways to choose a "color" for all triples is $$${n/3}\choose{n/6}$$$.
After choosing the color of each triple, let's choose how we actually color them. The triples are independent, so for each triple, we can introduce the coefficient $$$c_i$$$, which is the number of ways to color it so that its weight is maximized, and the triple has some specific type (either red or blue, doesn't matter since these are symmetric). Choosing the vertex which will be different from its neighbors is equivalent to choosing the edge which will not be included in the weight of the coloring (this is the edge which is not incident to the chosen vertex). So, $$$c_i$$$ is equal to the number of ways to choose that vertex in the $$$i$$$-th triple so that the weight is maximized; i. e. the weight of the edge not incident to the chosen vertex should be minimized. Thus, $$$c_i$$$ is just the number of minimum edge weights in the $$$i$$$-th triple.
The formula for the final answer is $$${{n/3}\choose{n/6}} \prod\limits_{i=1}^{n/3} c_i$$$.