OMC074(E)

　$1$ から $100$ の番号が付いた $100$ 個の頂点について, $pe\overbrace{p...p}^{n}er$ さんが素直ならば頂点 $n$ を白で塗り, $pe\overbrace{p...p}^{n}er$ さんが照れ屋さんならば頂点 $n$ を黒で塗る. さらに, 頂点 $n$ から頂点 $a_n$ へ有向辺を張ったグラフを考える. このグラフにおいて, どの辺も両端の頂点の色は異なり, どの頂点もただ一つの $2$ より大きな偶数個の頂点からなる閉路に含まれている. したがって, 特に白い頂点の数と黒い頂点の数は等しいことに注意する.

補題.　白い頂点 $W_1,W_2,\dots,W_n$ と黒い頂点 $B_1,B_2,\dots,B_n$ がある. このとき, これらの頂点の間に $2n$ 本の有向辺を張る方法であって, どの辺も両端の頂点の色は異なり, どの頂点もただ一つの偶数個の頂点からなる閉路に含まれているものは, $(n!)^2$ 通りある.
証明.　$W_i$ から出る辺の行き先を $B_{p_i}$, $B_i$ から出る辺の行き先を $W_{q_i}$ とすると, $p_1,p_2,\dots,p_n$ と $q_1,q_2,\dots,q_n$ はそれぞれ $1,2,\dots,n$ の置換である. また, 異なるグラフについて異なる置換が得られる.
　逆に, $p_1,p_2,\dots,p_n$ と $q_1,q_2,\dots,q_n$ をそれぞれ $1,2,\dots,n$ の置換とすると, $W_i\to B_{p_i}$, $B_i\to W_{q_i}$ と辺を張ることで, 条件をみたすグラフとなる.
　したがって, 条件をみたすグラフと置換 $\{p_i\},\{q_i\}$ の組は一対一対応するから, 示された.

　以下, $m$ を求めるため, 頂点の色を固定し, 包除原理を用いる. 黒と白の頂点 $1$ つずつからなる閉路 $k$ 個の選び方は $\left({}_{50}\mathrm{C}_k\right)^2k!$ 通りであるから $$m = {}_{100}\mathrm{C}_{50}\times \sum_{k = 0}^{50} (-1)^k\left({}_{50}\mathrm{C}_k\right)^2k!\bigl((50 - k)!\bigr)^2 = 100!\times \sum_{k = 0}^{50}\frac{(-1)^k}{k!}$$ を得る. 従って, それぞれの素数について計算することで求める答えは $50+26+12+10=\bf{98}$ である.