P15564 [CCPC 2025 Harbin Site] Connected Equilateral Triangles

Town A has $\frac{(n+1)(n+2)}{2}$ intersections. These intersections are connected by $3n$ **paths**, forming an equilateral triangle whose side length contains **$n$ roads**. The case $n=3$ is shown in the figure below. :::align{center}  ::: These $3n$ **paths** can be divided into three directions: left-slanted, horizontal, and right-slanted. Each direction contains $n$ **paths**. In each direction, the $i$-th **path** consists of $i$ **roads**. For example, when $n=3$: - The left-slanted **paths**, ordered by the number of **roads** from small to large, are $(6\leftrightarrow9)$, $(3\leftrightarrow5\leftrightarrow8)$, $(1\leftrightarrow2\leftrightarrow4\leftrightarrow7)$. - The horizontal **paths**, ordered by the number of **roads** from small to large, are $(2\leftrightarrow3)$, $(4\leftrightarrow5\leftrightarrow6)$, $(7\leftrightarrow8\leftrightarrow9\leftrightarrow10)$. - The right-slanted **paths**, ordered by the number of **roads** from small to large, are $(4\leftrightarrow8)$, $(2\leftrightarrow5\leftrightarrow9)$, $(1\leftrightarrow3\leftrightarrow6\leftrightarrow10)$. We call three **distinct** intersections $(u,v,w)$ an “equilateral triangle” triple of positive integer length $l$ if and only if, after **arbitrarily reordering $u,v,w$**, one of the following holds: - Starting from $u$, go through $l$ left-slanted **roads** to reach $v$; - Starting from $v$, go through $l$ horizontal **roads** to reach $w$; - Starting from $w$, go through $l$ right-slanted **roads** to reach $u$. Or: - Starting from $u$, go through $l$ right-slanted **roads** to reach $v$; - Starting from $v$, go through $l$ horizontal **roads** to reach $w$; - Starting from $w$, go through $l$ left-slanted **roads** to reach $u$. For example, in the figure above, $(2,4,5)$ and $(2,3,5)$ are “equilateral triangle” triples, while $(2,3,4)$ is not. To reduce traffic congestion, Town A decides to assign a direction to every **road**. After directing the roads, each **road** has a unique fixed direction, and all **roads** on the same **path** share the same direction. The figure below shows one possible orientation (corresponding to the third test case of Sample 1). :::align{center}  ::: We call three distinct intersections $(u,v,w)$ a “connected equilateral triangle” triple if and only if they form an “equilateral triangle” triple of positive integer length $l$ in the graph, and they can reach each other using only the $3l$ **roads** that form this “equilateral triangle” triple. For example, in the figure above: - $(2, 4, 5)$ is a “connected equilateral triangle” triple, because it is not only an “equilateral triangle” triple, but also they can reach each other using only the **roads** of that triangle $(2 \rightarrow 4,4 \rightarrow 5, 5 \rightarrow 2)$. - $(2, 3, 4)$ is not a “connected equilateral triangle” triple, because it is not an “equilateral triangle” triple. - $(2, 3, 5)$ is not a “connected equilateral triangle” triple, because although it is an “equilateral triangle” triple, they cannot reach each other using only the **roads** of that triangle $(5 \rightarrow 3, 3 \rightarrow 2, 2 \leftarrow 5)$. Now you are given the directions of all directed **paths**. Ask how many “connected equilateral triangle” triples there are in this graph.

This problem contains multiple test cases. The first line contains an integer $T$ ($1 \le T \le 10^5$), indicating the number of test cases. Then the test cases follow. For each test case: The first line contains an integer $n$ ($1 \le n \le 10^5$), indicating the size of the equilateral triangle. The second line contains a string $s1$ of length $n$, where $s1_i \in \{\text{0, 1}\}$. If $s1_i=\text{0}$, it means the direction of the left-slanted **path** consisting of $i$ **roads** is from upper-right to lower-left, and vice versa. The third line contains a string $s2$ of length $n$, where $s2_i \in \{\text{0, 1}\}$. If $s2_i=\text{0}$, it means the direction of the horizontal **path** consisting of $i$ **roads** is from left to right, and vice versa. The fourth line contains a string $s3$ of length $n$, where $s3_i \in \{\text{0, 1}\}$. If $s3_i=\text{0}$, it means the direction of the right-slanted **path** consisting of $i$ **roads** is from lower-right to upper-left, and vice versa. It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.

For each test case, output one integer, representing the number of “connected equilateral triangle” triples.

In Sample 1, the graph of the first test case is shown below. :::align{center}  ::: In Sample 1, the graph of the second test case is shown below. :::align{center}  ::: In Sample 1, the “connected equilateral triangle” triples in the third test case are: - $(2, 4, 5)$; - $(4, 7, 8)$; - $(5, 6, 9)$； - $(2, 7, 9)$. Translated by ChatGPT 5