かんプリンの学習記録

勉強したことについてメモしています. 主に競技プログラミングの問題の解説やってます.

ABC284 G - Only Once

ABC 典型数え上げ競技プログラミング解説

問題はこちら

目次

問題概要
解説
提出プログラム
感想

問題概要

${1}$ 以上 ${N}$ 以下の整数からなる長さ ${N}$ の整数 ${A}$ について， ${B_{i,1}=i}$ ， ${B_{i,j+1} = A_{B_{i,j}}}$ という数列 ${B_i}$ にちょうど一度だけ現れる数の種類を ${S_i}$ とする．
${A}$ として考えられる ${N^N}$ 個の数列全てにおいて ${\sum_{i=1}^{N}S_i}$ を求め，その総和を ${M}$ で割った余りを求めよ．

${1\leq N\leq 2×10^5}$
${10^8\leq M\leq 10^9}$

解説

対称性から、頂点 ${1}$ を基準に考えて最後に ${N}$ 倍することにします．

公式解説のようにグラフの問題として考えます．

すべてのFunctional Graphに対する「頂点 ${i}$ から辺を辿ったとき，ちょうど ${1}$ 回頂点 ${1}$ を訪れるような ${i}$ の数」の総和が答えになります．

あるグラフに対して，ちょうど ${1}$ 回頂点 ${1}$ を訪れるような ${i}$ はどのようになるのか考えてみましょう．

以下のように，赤の頂点を ${i}$ として選ぶと頂点 ${1}$ をちょうど ${1}$ 回訪れることが分かります．

赤い頂点からなる部分グラフは頂点 ${1}$ を根とする木となっていることが分かります．また，「頂点 ${1}$ をちょうど ${1}$ 回訪れる」という条件を満たすためには頂点 ${1}$ から赤い頂点以外の頂点に辺が張られている必要があります．

以上のことから「ちょうど ${1}$ 回頂点 ${1}$ を訪れるような ${i}$ の数」が ${k+1}$ となるようなグラフは次のように作ることができます．

頂点 ${1}$ を除く ${N-1}$ 個の頂点から ${k}$ 個を選ぶ
選んだ ${k}$ 個の頂点と頂点 ${1}$ を用いて木を作る
残りの ${N-1-k}$ 個の頂点から ${1}$ 個の頂点を選び，頂点 ${1}$ から辺を張る
${N-1-k}$ 個の頂点から ${N-1-k}$ 個の頂点に向かう辺を適当に張る

これらの選び方の数はそれぞれ以下のようになります．

${\binom{N-1}{k}}$
${(k+1)^{k-1}}$ (ケイリーの公式)
${N-1-k}$
${(N-1-k)^{N-1-k}}$

したがって，最終的なこの問題の答えは

$N×\sum_{k=0}^{N-2}\binom{N-1}{k}(k+1)^k(N-1-k)^{N-k}$

となります．任意modの二項係数を求める必要があることに注意してください．

nyaannyaan.github.io

提出プログラム

https://atcoder.jp/contests/abc284/submissions/37886440

感想

任意mod二項係数の話が一番難しい