P11391 [COCI 2024/2025 #1] 疑惑 / Zbunjenost

题目背景

译自 COCI 2024/2025 #1 T5。$\texttt{5s,0.5G}$。满分为 $120$。

题目描述

给定一个 $n$ 个顶点的凸包和它的三角剖分。

可以认为点按照顺时针顺序标号 $1\sim n$，也就是说，$\forall 1\le i\le n$，点 $i$ 和点 $(i\bmod n+1)$ 间有边相连。

定义一条长度为 $m$（$m\ge 3$）的简单回路 $a_0,a_1,\cdots,a_{m-1}$ 为满足以下条件的序列：

• $\forall i\in [0,m)$，$1\le a_i\le n$；
• $\forall 0\le i\lt j\lt m$，$a_i\neq a_j$；
• $\forall i\in [0,m)$，顶点 $a_i,a_{(i+1)\bmod m}$ 间有边相连。

定义两条回路本质相同，当且仅当一条回路可以通过翻转（reverse）或者循环移位或者翻转+循环移位得到另一条回路。

求出凸包内本质不同的回路条数，对 $(10^9+7)$ 取模。

输入格式

第一行，一个正整数 $n$。

接下来 $(n-3)$ 行，每行两个正整数 $x,y$，描述三角剖分的一条边。

输出格式

输出一行一个整数，表示答案对 $(10^9+7)$ 取模后的结果。

输入输出样例 #1

输入 #1

4 
1 3

输出 #1

3

输入输出样例 #2

输入 #2

5
1 3
3 5

输出 #2

6

输入输出样例 #3

输入 #3

6
2 4
4 6
6 2

输出 #3

11

说明/提示

样例解释

• 样例 $1$ 解释：$[1,2,3]$，$[1,4,3]$，$[1,2,3,4]$ 是合法的回路。
• 样例 $2$ 解释：$[1, 2, 3]$，$[1, 3, 5]$，$[3, 4, 5]$，$[1, 2, 3, 5]$，$[1, 3, 4, 5]$，$[1, 2, 3, 4, 5]$ 是合法的回路。
• 样例 $3$ 解释：$[1, 2, 6]$，$[2, 3, 4]$，$[4, 5, 6]$，$[2, 4, 6]$，$[1, 2, 4, 6]$，$[2, 3, 4, 6]$，$[2, 4, 5, 6]$，$[1, 2, 3, 4, 6]$，$[2, 3, 4, 5, 6]$，$[1, 2, 4, 5, 6]$，$[1, 2, 3, 4, 5, 6]$ 是合法的回路。

子任务

对于 $100\%$ 的数据，保证：

• $1\le n\le 2\times 10^5$；
• 给定的是合法三角剖分。

子任务编号	$n\le$	特殊性质	得分
$1$	$15$		$13$
$2$	$300$		$18$
$3$	$2\times 10^3$		$34$
$4$	$2\times 10^5$	A	$15$
$5$			$40$

• 特殊性质 A：$\forall 3\le i\le n-1$，点 $1$ 与点 $i$ 间有边相连。

#5697. 「COCI 2024/2025 #1」Zbunjenost

标签: 传统 | 时间限制: 5000 ms | 内存限制: 512 MiB |

题目描述

译自 COCI 2024/2025 Contest #1 T5「Zbunjenost」

Mr. Malnar 决定通过随机飞行来环游世界度过他的夏天。一段时间后，他发现自己身处一个未知国家的首都，那里的街道让他想起了三角剖分！更准确地说，这座城市由 $N$ 个有趣的地点组成（编号从 $1$ 到 $N$），并由 $2N-3$ 条街道连接。地点 $1, 2, \ldots, N$ 按顺序连接，形成一个具有 $N$ 个边的凸多边形。其余 $N-3$ 条街道以不相交的方式连接各个地点（端点处除外）。

在漫步这座国家首都的街道时，Mr. Malnar 发现自己回到了起点，且没有访问过任何地点超过一次。有点困惑的他意识到这是完全正常的，并提出了一个混乱度度量，即简单闭环的数量。简单闭环是一个位置序列 $V_{1}, V_{2}, \ldots, V_{m}$，使得对于每个 $i=1, 2, \ldots, m-1$，位置 $V_{i}$ 都通过街道与位置 $V_{i+1}$ 相连，且位置 $V_{m}$ 与 $V_{1}$ 相连。如果一个序列可以通过循环旋转或反转得到另一个序列，则这两个路径是等价的。例如，路径 $(1, 2, 3, 4)$ 与路径 $(2, 3, 4, 1)$ 等价。简单闭环是一组等价的路径。Mr. Malnar 现在请求你的帮助，来计算这座城市的混乱度！

输入格式

第一行是一个整数 $N$ $(1 \leq N \leq 2 \cdot 10^{5})$，表示有趣地点的数量。

在接下来的 $N-3$ 行中，每行包含整数 $X_{i}, Y_{i}$ $(1 \leq X_{i}, Y_{i} \leq N)$，表示第 $i$ 条街道连接的地点编号。

输出格式

在第一行输出该城市的混乱度，结果对 $10^{9}+7$ 取模。

样例 1

输入

4
1 3

输出

3

在草图中，每个环都用不同的颜色标出。

样例 2

输入

5
1 3
3 5

输出

6

代表环的路径有：$(1, 2, 3), (1, 3, 5), (3, 4, 5), (1, 2, 3, 5), (1, 3, 4, 5), (1, 2, 3, 4, 5)$。

样例 3

输入

6
2 4
4 6
6 2

输出

11

代表环的路径有：$(1, 2, 6), (2, 3, 4), (4, 5, 6), (2, 4, 6), (1, 2, 4, 6), (2, 3, 4, 6), (2, 4, 5, 6), (1, 2, 3, 4, 6), (2, 3, 4, 5, 6), (1, 2, 4, 5, 6), (1, 2, 3, 4, 5, 6)$。

数据范围与提示

详细子任务附加限制及分值如下表所示。

子任务	分值	附加限制
$1$	$13$	$N \leq 15$
$2$	$18$	$N \leq 300$
$3$	$34$	$N \leq 2000$
$4$	$15$	地点 $1$ 和 $k$ 对所有 $k=3, 4, \ldots, N-1$ 都有连接
$5$	$40$	无附加限制