titiaのノート: ケイリーの公式

　Cまで三完でした。

No.1665 quotient replace

　Grundy数を求めてACしたが、素因数の個数を考えることでNIMに帰着できたのね。なるほど。

　解説AC。

　二つ目の方法でやりました。二乗の個数が他の累乗の個数より多いことには気付いていたのに、こういう方法に思いつかなかったのはまずい。

　約数包除での方法も理解しました。コンテスト中は、素数ベキに絞ってやることを考えていた。そこから約数包除は遠いような近いような。

　解説AC。

　コンテスト中あまり考えなかったため解けなかったのは仕方ないけど、解説を見てすぐピンと来ないのは良くない。

・重複を除くため、残っている頂点のうち一番小さいものを何と組み合わせるかを考える

・ケイリーの公式

　この二つをちゃんと理解していれば解けたはずだし、どちらもそれほど特別な手法ではなかった。

　Dまで解いて、コンテスト期間が24時間もあるから残りは後で考えよう……、なんて思っていたらいつのまにか終わってしまった。（ごめんなさい）
　でも、復習したら、EもFも解けた気がしません……。頑張って検索すればいけたのかもしれないけど、自力では無理だったのは間違いない。

コンテストへのリンク

　解説AC。

　Aをソートするところは良いとして、n頂点の木の種類の求め方を知らなかった。ケイリーの公式というのがあるんですね。プリューファーコードによる木の全単射も面白い。

　解説AC。

　ラグランジュ補間は分かっていなかった。今回調べても、ちゃんと分かったとは言い難いけど……おおよその原理は分かったかなぁ。

　ついでに、えでゅふぉの類題もACしました。

　これは、PyPyではACできず、KotlinでAC。ただ、全部Long型で処理しようとしたらTLEしたため、Intとの使い分けが大変だった。modintってこういうとき必要なのね。

　なお、この問題も、pajenegodさんはPyPy3でACしている（1sを切ってる）のですが、どうやっているのでしょう……。