D - C4 解説 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.
Therefore, the answer is
\(\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})\).
This is equal to:
\((\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)!}\)
and this is FFT-friendly!
投稿日時:
最終更新: