　$q_n=p_{p_n}$ とする．頂点 $1,2,…,13$ に対して，各 $n$ について $n$ から $q_n$ への有向辺を張った有向グラフを $G$ とする． $G$ はいくつかの自己ループでないサイクルからなり，以下の事実が成り立つ．

- 任意のサイクルに対して，そのサイクル上の頂点を小さい順にそれぞれ $a_1,a_2,…,a_m$ とすると，これらはどの隣り合う二数も差が $1$ であり，
$$q_{a_1}=a_2, \quad q_{a_2}=a_3, \quad …, \quad q_{a_{m-1}}=a_m, \quad q_{a_m}=a_1$$

<details> <summary>
証明
<\/summary>
　$q_n\leq n-1$ なる $n$ が $l$ 個あり，小さい順に $b_1,b_2,…,b_l=13$ とすると，それ以外の $n$ では $q_n=n+1$ であるから， $q_{b_1},q_{b_2},…,q_{b_l}$ は $1,q_{b_1}+1,q_{b_2}+1,…,q_{b_{l-1}}+1$ のいずれかの値を取る． $q_{b_1}\leq b_1-1$ より， $q_{b_1}=1$ ．同様に帰納的に $q_{b_i}=b_{i-1}+1\quad(i\geq2)$ がいえる．このとき上記の事実が成り立つは明らか．
<\/details>

　$q_{…q_n}$ $(q$ の $i$ 回合成$)$ を $q^i(n)$ により表す．任意の長さ $k$ のサイクル $A$ 上の最小の頂点 $a$ について，下記のいずれかが成り立つとき，またそのときに限り $\lbrace p_n \rbrace$ は問題文の条件を満たす．

- ある別の長さ $k$ のサイクル $B$ 上のある頂点 $b$ に対して
$$p_{q^i(a)}=q^i(b), \quad p_{q^i(b)}=q^{i+1}(a) \quad (0\leq i\leq k-1)$$
となる．すなわち $A$ と $B$ のサイクルが交互に組み合わさった形である．

- $k$ が奇数かつ，
$$p_{q^i(a)}=q^{i+\frac{k+1}{2}}(a) \quad (0\leq i\leq k-1)$$
となる．

　$G$ は自己ループを持たず，長さが等しい偶数長のサイクルを奇数個持つことはないから，$G$ のサイクルの長さの組み合わせは
$$(13),(9,2,2),(7,3,3),(5,5,3),(5,4,4),(5,2,2,2,2),(3,3,3,2,2)$$ 
のいずれかである．

- $(13)$ のとき， $\dfrac{1!}{1!}\times 1=1$ （個）．
- $(9,2,2)$ のとき， $\dfrac{3!}{1!\times 2!}\times 1 \times 2=6$ （個）．
- $(7,3,3)$ のとき， $\dfrac{3!}{1!\times 2!}\times 1 \times (1+3)=12$ （個）．
- $(5,5,3)$ のとき， $\dfrac{3!}{1!\times 2!}\times (1+5) \times 1=18$ （個）．
- $(5,4,4)$ のとき， $\dfrac{3!}{1!\times 2!}\times 1 \times 4=12$ （個）．
- $(5,2,2,2,2)$ のとき， $\dfrac{5!}{1!\times 4!}\times 1 \times 12=60$ （個）．
- $(3,3,3,2,2)$ のとき， $\dfrac{5!}{3!\times 2!}\times (1+9) \times 2=200$ （個）．

　よって，条件を満たす $\lbrace p_n\rbrace$ の個数は $\mathbf{309}$ 個である．
公式解説
https://onlinemathcontest.com/contests/omc240/editorial/10345
0. ユーザー解説を書いた理由など

　公式解説は非常に端的にまとめられていてエレガントなのですが，本問を解けない人が解説を読み込むのは難しいのではないかと思い，できるだけ平易な表現で書いてみました．\
　かなり基本的なところから説明しているつもりなので，なかなか 400 点には挑めないという人でも読んでみてほしいです．\
　なお，公式解説を読んで普通に理解できる方は，読んでもあまり面白くないと思います．

---

1. $p_{p_n}$ の説明

　$\\{ p_n \\}$ は素直に見れば数列だが，関数として見ることもできる．\
　すなわち，集合 $S=\\{1,2,3, \cdots, 13\\}$ として，$S$ の元に $S$ の元を対応させる関数である（より正確に言えば，全単射の写像と言った方が良い）．\
　では $p_{p_n}$ とは何だろうか．\
　数 $n$ に対して，一度関数 $p$ で移して，再度関数 $p$ で移したものである．（下式）
$$n \xrightarrow{p} p_n \xrightarrow{p} p_{p_n}$$
　なお，以下の説明では，関数 $p$ を $2$ 回施したものを，$p^2$ で表しているところがある．すなわち
$$n \xrightarrow{p^2} p_{p_n}$$
　である．

---

2. サイクルを考える理由

　数 $n$ に対して，関数 $p$ を繰り返すことを考える．すなわち，次のような数列である．
$$n \xrightarrow{p} p_n \xrightarrow{p} p_{p_n} \xrightarrow{p} \cdots$$
　$p$ で移された値は，集合 $S$ の要素になり，集合 $S$ の要素は有限である．よって，この数列はどこかで，同じ数が $2$ 回現れる．その数を $a$ とすると，
$$a \xrightarrow{p} p_a \xrightarrow{p} \cdots \xrightarrow{p} a$$
となるわけである．要するに $p$ によるサイクルが存在することがわかる．

---

3. サイクルの例を考える

　まずは，最も基本である長さ $1$ のサイクルを考えよう．
　$$a \xrightarrow{p}  a$$
　である．このとき $p_{p_a}=a$ となり，問題文の条件に矛盾する．同様に，長さ $2$ のサイクルも矛盾する（確かめてみよ）．\
　次に，長さ $3$ のサイクルである．
　$$a \xrightarrow{p}  p_a \xrightarrow{p}  p_{p_a} \xrightarrow{p}  a$$
　ここで，$p_{p_n} \leq n-1$ が全ての $n$ で成り立てば明らかに矛盾する（$a \gt p_{p_a} \gt p_a \gt a$ である）．よって，少なくとも一つは $p_{p_n} = n+1$ を満たすものが存在する．そこで改めて
　$$a \xrightarrow{p}  p_a \xrightarrow{p}  a+1 \xrightarrow{p}  a$$
　とおこう．ここで $p_{p_n} \leq n-1$ が $2$ 回成り立てば（すなわち $a+1 \gt p_a \gt a$）矛盾である．よって，もう一度 $p_{p_n} = n+1$ を満たすものが存在する．このことから $p_a$ は $a+2$ か $a-1$ のいずれかであることがわかる．より一般化した表現をすれば，長さ $3$ のサイクルがあれば，そこに含まれる要素は連続した $3$ つの整数であることがわかる．

　続いて，長さ $4$ のサイクルである．簡単のため，
　$$a \xrightarrow{p}  b \xrightarrow{p}  c \xrightarrow{p} d \xrightarrow{p} a$$
としよう．まず $a$ と $c$ について見ると，

- $c \leq a-1$  or  $c=a+1$
- $a \leq c-1$  or  $a=c+1$

である．このことから $a,c$ は連続した $2$ つの整数であるとわかる．$b,d$ も同様である．

---

4. 長さ $k$ のサイクル

　長さが奇数のサイクルであれば，
$$n \xrightarrow{p} * \xrightarrow{p} * \xrightarrow{p} \cdots$$
　の代わりに
$$n \xrightarrow{p^2} * \xrightarrow{p^2} * \xrightarrow{p^2} \cdots$$
　を考えても，同じ長さのサイクルとなる（一応，$2$ と奇数が互いに素だからである）．\
　長さ $3$ のサイクルのときと同じように発想すれば，この長さ $k$ のサイクルの中には $k$ 個の連続する整数が存在する．

　長さが偶数のサイクルであれば，
$$n \xrightarrow{p} * \xrightarrow{p} * \xrightarrow{p} \cdots$$
　の代わりに
$$n \xrightarrow{p^2} * \xrightarrow{p^2} * \xrightarrow{p^2} \cdots$$
　を考えると，長さが半分のサイクルを得る．つまり，長さ $k=2l$ のサイクルは，長さ $l$ のサイクル二つに分離される．そして，そのどちらのサイクルも $l$ 個の連続する整数からなる．

---

5. 長さ $k$ のサイクルに対する場合の数

　長さが奇数 $k$ であるようなサイクルがあり，そこで使われる数は $1, 2, \cdots , k$ であるとしよう．このようなサイクルを構成する $p$ は何通り存在するだろうか（正確には 「$p$ の定義域を $1, 2, \cdots , k$ だけに狭めた関数」が何通りかを考えたい）．\
　この場合 $p$ は
$$1 \xrightarrow{p^2} 2 \xrightarrow{p^2} 3 \xrightarrow{p^2} \cdots k \xrightarrow{p^2} 1$$
　を満たし，そのような $p$ は一通りに定まる．

　次に，長さが偶数 $k=2l$ であるようなサイクルがあり，そこで使われる数は $1, 2, \cdots , l$ と $a+1, a+2, \cdots a+l$ であるとしよう．このようなサイクルを構成する $p$ は何通り存在するだろうか．残念ながら，奇数のときのように $1$ 通りではない．\
$$1 \xrightarrow{p^2} 2 \xrightarrow{p^2} \cdots l \xrightarrow{p^2} 1$$
$$a+1 \xrightarrow{p^2} a+2 \xrightarrow{p^2} \cdots a+l \xrightarrow{p^2} a+1$$
　の部分はそれぞれ一通りであるが，$1$ の行き先は $a+1, \cdots a+l$ のいずれでもよい．つまり，下式における $*$ の値が $l$ 通り存在する．
$$1 \xrightarrow{p} * \xrightarrow{p} 2 \cdots$$
　上式の $ * $ を決めれば $p$ は一つに定まるので，長さが偶数 $k=2l$ であるようなサイクルを構成する $p$ は $l$ 通りであることがわかった．

---

6. 問題を解く

　以上の議論から，$1,2,3, \cdots ,13$ を $3$ 個以上の連続する要素からなる集合（サイクルを構成する要素）に分け，それぞれに対する $p$ の個数を求めていけばよい．

- $(13)$ のとき， $1$ 通りである．
- $(10,3)$ のとき．長さ $10$ のサイクルの要素は，必ずしも連続する $10$ 個でなくても良かったことに注意せよ（具体例として $1,2,3,4,5,9,10,11,12,13$ でも長さ $10$ のサイクルを作れる）．数の選び方が $3$ 通り，さらに $p$ の作り方が $5$ 通りなので，$3×5=15$通り．
- $(9,4)$ のとき．数の選び方が $3$ 通り，さらに $p$ の作り方が $2$ 通りで，$3×2=6$ 通り．
- $(8,5)$ のとき．$3×4=12$ 通り．
- $(7,6)$ のとき．$3×3=9$ 通り．
- $(7,3,3)$ のとき．数の選び方が $3$ 通り．全てのサイクルの長さが奇数なので，これ以上考える必要はない．
- $(6,4,3)$ のとき．数の選び方が $\dfrac{5!}{2! \ 2!}$ 通り．さらに $p$ の作り方が $3×2$ 通りで，$30×6=180$ 通り．
- $(5,4,4)$ のとき．数の選び方が $\dfrac{5!}{2! \ 2! \ 2!}$ 通り．さらに $p$ の作り方が $2×2$ 通りで，$15×4=60$ 通り．
- $(5,5,3)$ のとき．数の選び方が $3$ 通り．
- $(4,3,3,3)$ のとき．数の選び方が $\dfrac{5!}{2! \ 3!}$ 通り．さらに $p$ の作り方が $2$ 通りで，$10×2=20$ 通り．

　場合分けが長かったが，以上を足し合わせればよい．

注）公式解説と場合分けが異なるのは，公式解説の $(7,3,3)$ の中に本解説の $(7,6)$ も含められているからである．また，公式解説の $(5,4,4)$ は本解説でいう $(8,5)$ を表しているなど，微妙に異なる点に注意せよ．
より平易な表現による解説
https://onlinemathcontest.com/contests/omc240/editorial/10345/779
本質的に公式解説と異なるわけではないので、公式解説がわかってない人はまず公式解説を読んでください。

直接$i \rightarrow p_i$のグラフを考えます。適当な考察により、奇数長のサイクルはある連続した数からなり、その連続した奇数個の数を固定したときサイクルとして$1$通りしかないことがわかります。また、偶数長の時は、ある$2$つの連続した$k$個の数からなり、$2$つを交互に並べたものになるため、$2$つの連続した数を決め打ったときサイクルは$k$通りあることがわかります。よって、題意の条件を満たす$p$の数え上げについて、まず連続した数のかたまりの個数を決め打ち、次に連続したかたまりごとに奇数長のサイクルか偶数長のサイクルか割り当てを決め、最後に連続したかたまりごとの連続する長さを決め打つという決め方を考えると、以下の式が答えと等しいことがわかります。

ここで、連続したかたまりの個数を$k$とすると、連続したかたまりの長さが$2$以上であることや、$k$個のかたまりの偶奇サイクルの割り当ての決定などを踏まえると、$k$について$13≡k \pmod 2$かつ$2k \leq 13$が必要であることに注意してください。また、立式の過程で典型的な数え上げ問題が含まれていますが、ここでは説明は割愛し、その答えを用いて以下に式を示しています。

$$\displaystyle\sum_{k \in \\{1,3,5 \\}} \sum_{l=0}^{\left\lfloor \frac{k}{2} \right\rfloor} \frac{k!}{l!(k-2l)!2^l}\sum_{m=0}^l (-1)^m 2^{l-m}\binom{\frac{13-3k+2l-2m}{2}}{k-1}$$

この式を計算することにより本問題の答え$309$を得ることができます。
公式解説がわかる人向けのエレガントな解法
https://onlinemathcontest.com/contests/omc240/editorial/10345/781
　$1,2,…,13$ の順列 $p_1, p_2, \ldots, p_{13}$ であって以下が成り立つようなものはいくつありますか．
- $13$ 以下の任意の正整数 $n$ について，$p_{p_n}$ は $n-1$ 以下であるか，または $n+1$ に等しい．