| For All Solvers
OMC074 (for experts)

OMC074(E)

ユーザー解説 by zplc

　最後に運営さんから補足があるので是非そちらを併せて読んでください．

　1,2,⋯ ,1001,2,\cdots, 100 を頂点とし nn から ana_n に辺を張った有向グラフを考える．このとき条件より各連結成分は周期が 44 以上の偶数のサイクルであり，サイクルが kk 個のとき村人の性格は 2k2^k 通りある．
　例として周期 44 のサイクルが 2222 個，66 のサイクルが 22 個の場合を考えよう．このとき問題の組み合わせは 100!(4!)22×(6!)2×122!⋅2!×(3!)22×(5!)2×222+2=100!222×32×122!⋅2!\frac{100!}{(4!)^{22}\times (6!)^2}\times \frac{1}{22!\cdot 2!} \times (3!)^{22}\times (5!)^2\times 2^{22+2}=\frac{100!}{2^{22}\times 3^2}\times \frac{1}{22!\cdot 2!} 通りである．ここで，右辺をさらに以下のように変形する： 100!24!×1222×32×24!22!⋅2!\frac{100!}{24!}\times \frac{1}{2^{22}\times 3^2}\times \frac{24!}{22!\cdot 2!} このとき以下に留意する：

  • 2×22+3×2=502\times 22+3\times 2=50
  • 第3項は 2222 個の 22 と 22 個の 33 を並べ替える方法の総数になっている．

　この要領で，連結成分の個数が kk 個である場合，問題の組み合わせの総数は以下の形式的冪級数の x50x^{50} の係数で与えられることが分かる． 100!k!(x22+x33+x44+⋯ )k\frac{100!}{k!}\left(\frac{x^2}{2}+\frac{x^3}{3}+\frac{x^4}{4}+\cdots\right)^k これを k=1,2,⋯k=1,2,\cdots について足し合わせることで，結局求めるべき mm は以下で表される Q(x)Q(x) の x50x^{50} の係数で与えられる． P(x)=x22+x33+x44+⋯ ,　Q(x)=100!1!P(x)+100!2!P(x)2+100!3!P(x)3⋯P(x)=\frac{x^2}{2}+\frac{x^3}{3}+\frac{x^4}{4}+\cdots,　Q(x)=\frac{100!}{1!}P(x)+\frac{100!}{2!}P(x)^2+\frac{100!}{3!}P(x)^3\cdots ここで P′(x)=x+x2+x3+⋯P^\prime (x) = x+x^2+x^3+\cdots だから Q′(x)=P′(x)(100!0!+100!1!P(x)+100!2!P(x)2+⋯ )=(x+x2+x3+⋯ )(100!+Q(x))\begin{aligned} Q^\prime(x)&=P^\prime (x) \left(\frac{100!}{0!}+\frac{100!}{1!}P(x)+\frac{100!}{2!}P(x)^2+\cdots\right) \\ &= (x+x^2+x^3+\cdots)(100!+Q(x)) \end{aligned} Q(x)=a0+a1x+a2x2+⋯Q(x)=a_0+a_1 x+ a_2 x^2+\cdots とおけば m=a50m=a_{50} であり， Q′(x)=a1+2a2x+3a3x2+⋯=(a0+100!)x+(a0+a1+100!)x2+(a0+a1+a2+100!)x3+⋯\begin{aligned} Q^\prime(x) &= a_1+2a_2x+3a_3x^2+\cdots \\ &= (a_0+100!)x+(a_0+a_1+100!)x^2+(a_0+a_1+a_2+100!)x^3+\cdots \end{aligned} 係数比較と a0=a1=0a_0=a_1=0 より以下が得られる： a2=100!2,　a3=100!3,　ak+2=100!+∑i=2kaik+2　(k=2,3,⋯ )a_2=\frac{100!}{2},　a_3=\frac{100!}{3},　a_{k+2}=\frac{100!+\sum_{i=2}^{k} a_i}{k+2}　(k=2,3,\cdots) あとは a50a_{50} が 2,3,5,72,3,5,7 でそれぞれ割り切れる回数を求めればよい．bn=an100!b_n=\dfrac{a_n}{100!} とおけば，帰納的に bnb_n は以下に等しいことが分かる：

  • 正整数からなる狭義単調減少な有限数列であって，初項が nn であり，連続する 22 項の差が常に 22 以上であるようなものすべてについて，項の総積の逆数を足し合わせた値．

例えば n=6n=6 のときは b6=16×4×2+16×4+16×3+16×2+16b_6=\frac{1}{6\times 4\times 2}+\frac{1}{6\times4}+\frac{1}{6\times 3}+\frac{1}{6\times 2}+\frac{1}{6} である．以下 2,3,5,72,3,5,7 それぞれについて b50b_{50} のオーダーを考える（便宜上負の値も考える）．

  • 22 のとき {50,48,46,⋯ ,2}\{50,48,46,\cdots,2\} のときのみオーダーが最小値 −47-47 を取り，b50b_{50} のオーダーは −47-47 である．
  • 33 のとき {50,48,45,⋯ ,3}\{50,48,45,\cdots,3\} のときのみオーダーが最小値 −22-22 を取り，b50b_{50} のオーダーは −22-22 である．
  • 55 のとき {50,※,45,※,40,⋯ ,10,※,5,※}\{50,※,45,※,40,\cdots,10,※,5,※\} の形式で表される数列のときにオーダーが最小値 −12-12 を取り，b50b_{50} のオーダーも −12-12 であることが計算により確認できる．
  • 77 のとき {50,※,42,※,35,⋯ ,14,※,7,※}\{50,※,42,※,35,\cdots,14,※,7,※\} の形式で表される数列のときにオーダーが最小値 −6-6 を取り，b50b_{50} のオーダーも −6-6 であることが計算により確認できる．

以上より，求める値は (97−47)+(48−22)+(24−12)+(16−6)=98(97-47)+(48-22)+(24-12)+(16-6)=\textbf{98} である．

（運営補足）形式的冪級数として P,QP,Q は次のように計算でき，これより本解説における mm の表式を得ることもできます． P(x)=−log⁡(1−x)−x,Q(x)=100!(eP(x)−1)=100!(e−x1−x−1)=100!(∑k≥0(−x)kk!)(∑k≥0xk)−100!=100!∑n≥1(∑0≤k≤n(−1)kk!)xn\begin{aligned} P(x)&=-\log(1-x)-x,\\ Q(x)&=100!(e^{P(x)}-1)\\ &=100!\left(\dfrac{e^{-x}}{1-x}-1\right)\\ &=100!\left(\sum_{k\geq 0}\dfrac{(-x)^k}{k!}\right)\left(\sum_{k\geq 0}x^k\right)-100!\\ &=100!\sum_{n\geq 1}\left(\sum_{0\leq k\leq n}\dfrac{(-1)^k}{k!}\right)x^n \end{aligned}