atcoder.jp N!の総和系なので、確率・期待値でやるべき問題。 まずは1回のコストの期待値を考える。答えはこれにN!をかけてやればよい。すると、ブロックj を取り除いたときに、ブロックiが連結である確率をP(i, j)としたとき、1回のコストの期待値はΣa[i] *…

atcoder.jp xを有理数(つまり、整数とは限らない)として、x(x+1)(x+2)...とみなすと、剰余代数系ではある整数yが存在して y(y+1)(y+2)... を計算するのとおなじになる。これが最重要。 x(x+d)(x+2d)... = d^n * y(y +1) ... (y+n-1) (ただしy=x*d^(-1) mod 1…

atcoder.jp なんとかこういう問題の本質がわかった気がする。 まず状態遷移を考えると、今までにAがi回勝って、Bがj回勝った、という状態をS(i, j) とおく。これに引き分けがk回あった、という状態を考えてしまうと引き分けは永遠に続くことがあるので、状態…