ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

HUPC2020Day1 F: n 角錐グラフ

問題
提出コード

解法

頂点0と別の頂点を結ぶ辺の集合を中心の辺、pとp+1を結ぶ辺の集合を円周上の辺と呼ぶことにします。
i回頂点0に戻る、と仮定したときの数え方が高速に求まれば、これを全部のiについて試せばよいです。
このとき、頂点0を1回だけ通る閉路はi個あるはずです。よって、今回見ているサーキットは、中心の辺がN本の中からi本、円周上の辺はN本からk-2i本選ばれていることになります。
これらの閉路を通る順番はなんでもよく、また、閉路を時計回りに進むか、反時計回りに進むかはそれぞれの閉路ごとに独立に考えられます。よって、最後にi! \times 2^{i}をかける必要があります。
次に、上記の閉路で使う辺のパターンを数えます。
同じ辺を2回以上通れないことから、
(辺を通る区間)(辺を通らない区間)(辺を通る区間)...(辺を通らない区間)
となっているはずです。辺を通る区間、通らない区間は丁度i個になっています。
辺を通る区間の1つが、1,2,...kであると固定します。そうすると、このときの区間の決め方を数えたときに、\frac{N}{i}をかければ、全体での辺の決め方を数えられたことになります(先頭を固定したので、その先頭をN頂点全てに経験させる必要がありますが、先頭のそれぞれの閉路パターンで、先頭の選び方はi通りあります。よってこの値をかければよいです)。
このとき、辺を通る区間、通らない区間それぞれ独立に考えると、
辺を通る区間:_{i}H_{k - 3i}通り
辺を通らない区間:_{i}H_{n - (k-2i) - i}通り
で数えられます。
選ばなければいけない辺の本数がそれぞれ決まっていて、i個の区間に最低1本ずつ割り振る必要があるので、まず1本ずつ割り振った後に、重複組み合わせを考えればよいです。
さて、これにより辺k本を通るサーキットの個数が

  • i! \times 2^{i} \times _{i}H_{k - 3i} \times _{i}H_{n - (k-2i) - i} \times \frac{N}{i}

で求められることがわかりました。
あとは重みの総和ですが、中心の辺が選ばれる確率は\frac{k-2i}{N}、円周上の辺が選ばれる確率は\frac{2i}{N}なので、これをb_i,a_iにかけてあげた後、上記の通り数をかければ答えが求まります。

感想

悩みましたが、実際に数え上げてみると求める解は想像以上に綺麗になるので面白かったです。