　頂点を $8$ つ持ち，$i=1,2,\ldots,8$ について頂点 $i$ から頂点 $p_i$ に辺を張ったグラフを考える．また，それぞれの頂点を何種類かの色で塗る．ただしこのとき，対応するひよこが同じ箱に入っているなら同じ色で塗り，異なる箱に入っているなら異なる色で塗る．このように塗り分けることで，元の問題はグラフを最適彩色する問題に帰着された．次の補題を示そう．

---

**補題.**　$n$ を $2$ 以上の整数とし，$G_n$ を $n$ 頂点 $v_1,v_2,\ldots,v_n$ からなり $v_1→v_2→ \cdots →v_n→v_1$ のように辺を張ったグラフとする．このとき，$G_n$ を最適彩色するために必要な色数は，$n$ が奇数のとき $3$ 色，偶数のとき $2$ 色である．

**証明.**　\
　$n$ が偶数のとき，明らかに $1$ 色では不可能なため $2$ 色以上である．逆に，$2$ 色を交互に塗ることで可能である．\
　$n$ が奇数のとき，明らかに $1$ 色では不可能であり，$2$ 色ではどちらか一方の色が $\dfrac{n+1}{2}$ 個以上必要なため，どこかで同じ色が隣り合ってしまい不可能である．逆に，ある $1$ 頂点を $1$ 色で塗り，残りの頂点を別の $2$ 色で交互に塗ることで $3$ 色で可能である．

---

　さて，元のグラフはいくつかの閉路に分けられ，その分け方は次の $7$ つに限られる．
$$G_8,G_6+G_2,G_5+G_3,G_4+G_4$$
$$G_4+G_2+G_2,G_3+G_3+G_2,G_2+G_2+G_2+G_2$$
　必要な箱の個数は，$G_{奇数}$ が少なくとも $1$ つ含まれれば $3$ 個，含まれなければ $2$ 個であるため，$G_3+G_3+G_2,G_5+G_3$ の場合のみが $3$ 個となる．これらはそれぞれ
$$({}_8 \mathrm C_2×{}_6 \mathrm C_3÷2)×(3-1)!×(3-1)!×(2-1)!=1120$$
$${}_8 \mathrm C_3×(5-1)!×(3-1)!=2688$$
通り存在するから，求める答えは $2×14833+(1120+2688)=\mathbf{33474}$ である．
公式解説
https://onlinemathcontest.com/contests/omc190/editorial/8459
　Bonus：一般にひよこが $N$ 匹いる場合の答え $f(N)$ を，ある程度簡単な形で表す．

---

　まず $(1,\dots,n)$ の並び替え $(P_1,\dots,P_n)$ で $P_i\neq i$ を満たすものの個数を求めよう．
このような並び替えは**攪乱順列**と呼ばれ，その個数を $g(n)$ とおけば次が成り立つ．
$$g(n)=\sum_{k=0}^{n}\binom{n}{k}(-1)^k(n-k)!$$

<details>
<summary>証明<\/summary>
　包除原理を用いる．\
　$1\leq i\leq n$ に対して，$(1,\dots,n)$ の並び替え $(P_1,\dots,P_n)$ で $P_i=i$ を満たすもの全体の集合を $A_i$ と定める．
このとき $I\subset\\{1,\dots,n\\},I\neq\emptyset$ に対し $\left|\bigcap_{i\in I}A_i\right|=(n-|I|)!$ であることは容易にわかるから，包除原理より
$$\begin{aligned}
|A_1\cup\cdots\cup A_n|
&=\sum_{I\subset\\{1,\dots,n\\},I\neq\emptyset}(-1)^{|I|-1}\left|\bigcap_{i\in I}A_i\right|\\\\
&=\sum_{I\subset\\{1,\dots,n\\},I\neq\emptyset}(-1)^{|I|-1}(n-|I|)!\\\\
&=\sum_{k=1}^{n}\binom{n}{k}(-1)^{k-1}(n-k)!\\\\
\end{aligned}$$

となる．$A_1\cup\cdots\cup A_n$ は $(1,\dots,n)$ の並び替え $(P_1,\dots,P_n)$ であって，ある $i$ で $P_i=i$ をみたすもの全体の集合なので，求める値 $g(n)$ は $g(n)=n!-|A_1\cup\cdots\cup A_n|$ として得られる．

<\/details>

　実際に $n=8$ として計算してみれば $g(8)=14833$ が成り立ち，問題で与えられた値と一致することが確認できる．

　元の問題に戻ろう．公式解説の補題の部分までは公式解説と同様である．公式解説のように順列から作られるグラフを**正しいグラフ**と呼ぶことにする．このとき，正しいグラフはいくつかのループからなる有向グラフである．補題を踏まえれば，$f(N)=3g(N)-($ 偶数長の閉路しか含まない $N$ 頂点の正しいグラフの個数 $)$ である．\
　偶数長の閉路しか含まない $N$ 頂点の正しいグラフの個数を求めたい．結論から述べれば，それは $N$ が奇数のとき $0$，$N$ が偶数のとき $((N-1)!!)^2$ である（ $!!$ は二重階乗）．

<details>
<summary>解法1：組み合わせ論的に解く<\/summary>
　$N$ が奇数のとき $0$ なのは明らかである．以下 $N$ は偶数であるとし，偶数長の閉路しか含まない $N$ 頂点の正しいグラフを**良いグラフ**と呼ぶことにする．\
　各良いグラフについて，次の操作Aによって $N$ 頂点を $N\/2$ 個のペアに分ける分け方（以下**正しい分け方**とする）が得られる．ただし，ペア内の順序，ペア間の順序はいずれも区別しない．

- **操作A**：各閉路において頂点番号が最小の頂点から $2$ 個ずつに区切る（例：$4\to 2\to 1\to 3\to 4$ を $(1,3),(2,4)$ にする）．

これによって，各良いグラフから正しい分け方が $1$ つずつ得られる．逆に，各正しい分け方に対し次の操作を考える．

- **操作B**：「ペア内の頂点番号の最小値」が小さい順にペアを並び替え，各ペアに含まれる頂点を順にグラフに追加していく．これまでに $k$ ペア追加済みであるとき，次のペア $(u,v)\ (u\lt v)$ は次のいずれかを満たすように追加する．
  - 新しい連結成分として長さ $2$ の閉路 $u\to v\overset{\star}\to u$ を追加する．この追加の仕方は一意．
  - すでにある辺のうち $\star$ のついた辺（$k$ 本ある）のいずれか一つを選ぶ．その辺を $x\overset{\star}\to y$ としたとき，その辺を削除した上で $x\overset{\star}\to u\to v\overset{\star}\to y$ または $x\overset{\star}\to v\to u\overset{\star}\to y$ となるよう辺を追加する．この追加の仕方は $2k$ 通り．

このとき，次のようなことが確認できる．

- 任意の正しい分け方に対し，どのように操作Bを行っても得られるグラフは良いグラフであり，そのグラフに操作Aを行うと元の正しい分け方が得られる．また操作B内での操作の方法は $1\cdot 3\cdot\cdots\cdot(N-1)=(N-1)!!$ 通りあるが，最終的にできるグラフは全て相異なる．
- 任意の良いグラフに対し，それに操作Aを行って得られる正しい分け方について，操作Bを適切に行えば元の良いグラフが復元できる．

従って，操作A・操作Bによって正しい分け方 $1$ つに対し良いグラフが $(N-1)!!$ 個対応する．正しい分け方，すなわち $N$ 頂点を $N\/2$ 個のペアに分ける分け方は $(N-1)!!$ 通りあるから，良いグラフは $((N-1)!!)^2$ 個存在する．

<\/details>
<details>
<summary>解法2：形式的冪級数を用いる<\/summary>

　$k\geq 1$ に対して，長さ $2k$ の閉路が $b_k$ 個含まれる $N$ 頂点の正しいグラフの個数は次のように表せる．
$$\frac{N!}{\prod_{k\geq 1}b_k!((2k)!)^{b_k}}\cdot\prod_{k\geq 1}\left((2k-1)!\right)^{b_k}=N!\prod_{k\geq 1}\frac{1}{b_k!}\left(\frac{1}{2k}\right)^{b_k}$$

　従って，偶数長の閉路しか含まない $N$ 頂点の正しいグラフの個数は次の形式的冪級数の $x^N$ の係数に等しい．
$$N!\prod_{k\geq 1}\left(\sum_{i\geq 0}\frac{1}{i!}\left(\frac{x^{2k}}{2k}\right)^{i}\right)$$

　ここで，上式は次のように変形していくことができる．
$$\begin{aligned}
N!\prod_{k\geq 1}\left(\sum_{i\geq 0}\frac{1}{i!}\left(\frac{x^{2k}}{2k}\right)^{i}\right)
&=N!\prod_{k\geq 1}\exp\left(\frac{x^{2k}}{2k}\right)\\\\
&=N!\exp\left(\sum_{k\geq 1}\frac{x^{2k}}{2k}\right)\\\\
&=N!\exp\left(\frac{1}{2}\sum_{n\geq 1}\frac{x^n+(-x)^n}{n}\right)\\\\
&=N!\exp\left(-\frac{\log(1-x)+\log(1+x)}{2}\right)\\\\
&=N!\left((1-x)(1+x)\right)^{-1\/2}\\\\
&=N!(1-x^2)^{-1\/2}
\end{aligned}$$

　最終的な式の $x^N$ の係数は $N$ が奇数のとき $0$，偶数のとき $N!\cdot\dfrac{(N-1)!!}{N!!}=((N-1)!!)^2$ である．

<\/details>

　求める値 $f(N)$ は
$$f(N)=3\sum_{k=0}^{N}\binom{N}{k}(-1)^k(N-k)!-\begin{cases}
0&(N:\text{odd})\\\\
((N-1)!!)^2&(N:\text{even})
\end{cases}$$
となる．$N=8$ とすれば $f(8)=3\cdot 14833-(7!!)^2=33474$ となり，元の問題の答えと確かに一致する．
ひよこの匹数を一般化
https://onlinemathcontest.com/contests/omc190/editorial/8459/352
　OMC君はひよこを箱に入れて分ける仕事をしています．ひよこは全部で $8$ 匹おり，それぞれひよこ $1,2,\ldots,8$ と呼ばれています．いま，OMC君は社長から $(1,2,\ldots,8)$ の並び替え $(p_1,p_2,\ldots,p_8)$ であって，任意の $1\le i \le 8$ について $i\neq p_i$ なるものを伝えられ，さらに次の指示を受けました：

- $i=1,2,\ldots,8$ について，ひよこ $i$ とひよこ $p_i$ は別の箱に入れること．

ただし，OMC君は箱を十分にたくさん持っているものとします．\
　並べ替え $(p_1,p_2,\ldots,p_8)$ としてありうるものは全部で $14833$ 個ありますが，それぞれについて必要な箱の個数の最小値を求め，それらの総和を求めて下さい．