No.2381 Gift Exchange Party
解説AC。
こういう問題で、iからA[i]に辺を張ったグラフを考えるのは典型。Pが素数なので、そのグラフにおけるサイクルが全て1かPになれば良い。
コンテスト中は、Pが素数だということを読み飛ばしていた。が、このグラフすら考えていなかったのは反省。サイクルが～みたいなことをぼんやりと考えていたはずだが、何を考えていたのだろう……。
また、実装はTester解説の方法でやったが、累積積による高速化が必要なことに気付かなかったりして手間取った。
DPでやるのが簡単なのですね。今まで使っていない最も小さな数に注目するのが良いのか。それならPが素数じゃなくても解ける。形式的ベキ級数でも扱えるらしい。
No.2383 Naphthol
バーンサイドの公式について、高校数学の美しい物語を参考にしながらAC。
modを取っているのに、（*pow(4,mod-2,mod)とせず）4で割っていて答えが合わず困ったのは恥ずかしい。
0 件のコメント:
コメントを投稿