結局、フェルマーの小定理から x = i のとき 1 で、それ以外の時に 0 となるような p-1 次式が作れてしまうというだけの問題。賢い。 あとは a[ i ] = 1 のときに毎回 1 - (x-i)^(p-1) の係数を二項定理で作るだけ。 p = int(input()) a = list(map(int, inp…

約数系の包除原理の問題として解いたけど、どう帰着するのかわからなかった。 まず lcm ではなくて最大公約数 gcd で考える。 lcm( i,k ) = i*k//gcd( i,k ) で求まる。 すると、1 ≦ i ≦ n, k なので、k の約数の集合を g とすると、g = gcd( i,k ) になる i…

k = 0 から順番に (A[k*2],B[k*2]), (A[k*2+1],B[k*2+1]) を (A[k*2]+B[k*2])*A[k*2+1]+B[k*2+1] と計算していく問題。 セグ木を使うと、(A[k*2]*A[k*2+1], B[k*2]*A[k*2+1]+B[k*2+1]) の結果を (A[k], B[k])に保存できるので、求める答えは sum(A[1]+B[1]) …

diff が一つ上がるごとに発想が一つ増える感じがする。 緑なら一つ、青diff なら二つといったイメージ 今回の問題は橙diff で実験から３つのことが分かるかどうかみたいな問題だった。1. ボール i が衝突を考慮しないで t 秒たったときの位置には 1 ~ n まで…