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回あった、という状態を考えてしまうと引き分けは永遠に続くことがあるので、状態…