P16085 [ICPC 2024 NAC] Dihedral Group

In mathematics, the dihedral group $ D_n $ is the group of symmetries of a regular $ n $-gon. Rotations and reflections are elements of $ D_n $, and in fact all elements of the dihedral group can be expressed as a series of rotations and reflections. Elements of $ D_n $ act on the $ n $-gon by permuting its vertices. For example, consider a regular pentagon with vertices initially labeled $ 1, 3, 5, 4, 2 $ (clockwise, starting from the top): :::align{center}  ::: Applying the above three dihedral actions to the pentagon (a rotation, reflection, and then another rotation) produces the following relabelings of the pentagon’s vertices: $$ 1, 3, 5, 4, 2 \rightarrow 2, 1, 3, 5, 4 \rightarrow 2, 4, 5, 3, 1 \rightarrow 1, 2, 4, 5, 3. $$ You are given an arbitrary clockwise labeling of the vertices of a regular $ n $-gon using the integers $ 1 $ through $ n $, and a second sequence to test. Determine whether it’s possible to apply some series of dihedral actions to the $ n $-gon so that the test sequence appears as a contiguous clockwise sequence of vertex labels on the transformed polygon.

The first line of input has two integers $ n $ and $ m $, ($ 1 \le m \le n \le 5 \cdot 10^4 $) where $ n $ is the number of vertices of the polygon and $ m $ is the length of the sequence to be tested. The next line contains $ n $ space-separated integers $ d $ ($ 1 \le d \le n $). This is the initial labeling of the polygon vertices. It is guaranteed that each integer from $ 1 $ to $ n $ appears exactly once. The next line contains $ m $ space-separated integers $ t $ ($ 1 \le t \le n $). This is the sequence to be tested.

Output a single integer, which is $ 1 $ if the test sequence could appear as a contiguous sequence of vertex labels after applying some series of dihedral actions to the initial polygon, and $ 0 $ otherwise.