Contest Duration: - (local time) (270 minutes) Back to Home

## D - C4 Editorial by rng58_admin

Let’s split the entire walk into sections of lengths $$2$$. For example, we see $$S \rightarrow T \rightarrow U \rightarrow V \rightarrow S$$ as a concatenation of two sections $$S \rightarrow T \rightarrow U$$ and $$U \rightarrow V \rightarrow S$$. Since C4 is a bipartite graph, we have only $$8$$ possible types of sections. We divide them into three categories:

• $$T$$-crossing types: $$S \rightarrow T \rightarrow U$$ and $$U \rightarrow T \rightarrow S$$.
• $$V$$-crossing types: $$S \rightarrow V \rightarrow U$$ and $$U \rightarrow V \rightarrow S$$.
• Returning types: $$S \rightarrow T \rightarrow S$$, $$S \rightarrow V \rightarrow S$$, $$U \rightarrow T \rightarrow U$$, and $$U \rightarrow V \rightarrow U$$.

Let’s fix the number of $$T$$-crossing sections (call it $$i$$) and $$V$$-crossing sections (call it $$j$$). Then, the total number of valid walks is the product of the following values:

(Here we denote $$C(x, y) := \binom{x+y}{x}$$, the number of ways to arrange $$x$$ items and $$y$$ items. Define $$C(x, y, z)$$ similarly. Assume that it is zero for invalid indices)

• First let’s choose the types and relative orders of $$T$$-crossing sections and $$V$$-crossing sections. There are $$C(i, j)$$ ways to do so.
• Then, insert returning sections of types $$S \rightarrow T \rightarrow S$$ and $$S \rightarrow V \rightarrow S$$. There are $$C(\frac{i+j}{2}, \frac{a-i}{2}, \frac{d-j}{2})$$ ways.
• Then, insert returning sections of the two other types. There are $$C(\frac{i+j}{2} - 1, \frac{b-i}{2}, \frac{c-j}{2})$$ ways.

$$\sum_{i,j} C(i, j) C(\frac{i+j}{2}, \frac{a-i}{2}, \frac{d-j}{2}) C(\frac{i+j}{2} - 1, \frac{b-i}{2}, \frac{c-j}{2})$$.
$$(\frac{a+d}{2})! (\frac{b+c}{2}-1)! \sum_{i,j} \frac{(i+j)!}{((i+j)/2)!((i+j)/2+1)!} \cdot \frac{1}{i!((a-i)/2)!((b-i)/2)!} \cdot \frac{1}{j!((c-j)/2)!((d-j)/2)!}$$