P16085 [ICPC 2024 NAC] Dihedral Group

在数学中，二面体群 $ D_n $ 是正 $ n $ 边形的对称群。旋转和反射都是 $ D_n $ 的元素，实际上，二面体群的所有元素都可以表示为一系列旋转和反射的复合。$ D_n $ 的元素通过置换顶点来作用于 $ n $ 边形。例如，考虑一个正五边形，其顶点初始标记为 $ 1, 3, 5, 4, 2 $（顺时针方向，从顶部开始）： :::align{center}  ::: 将上述三个二面体作用（一次旋转、一次反射、再一次旋转）应用到五边形上，会得到以下顶点标记的重排： $$ 1, 3, 5, 4, 2 \rightarrow 2, 1, 3, 5, 4 \rightarrow 2, 4, 5, 3, 1 \rightarrow 1, 2, 4, 5, 3. $$ 你得到一个正 $ n $ 边形的顶点标记（使用整数 $ 1 $ 到 $ n $，按顺时针顺序给出），以及一个待测试的序列。请判断是否存在一系列二面体群作用，使得在变换后的多边形上，该测试序列作为顶点标记的连续顺时针子序列出现。

输入的第一行包含两个整数 $ n $ 和 $ m $（$ 1 \le m \le n \le 5 \cdot 10^4 $），其中 $ n $ 是多边形的顶点数，$ m $ 是待测试序列的长度。 下一行包含 $ n $ 个空格分隔的整数 $ d $（$ 1 \le d \le n $）。这是多边形顶点的初始标记。保证 $ 1 $ 到 $ n $ 的每个整数恰好出现一次。 下一行包含 $ m $ 个空格分隔的整数 $ t $（$ 1 \le t \le n $）。这是待测试的序列。

输出一个整数，如果存在一系列二面体群作用，使得测试序列作为初始多边形变换后顶点标记的连续子序列出现，则输出 $ 1 $，否则输出 $ 0 $。

翻译由 DeepSeek V3.2 完成