多項式の値、f(0), f(1), …, f(N)が与えられるから、f(T)を出力しろ、という問題。 単純にラグランジェ補間でよい。 逆元を求める際はextgcdとmod_inverseを使ってあげる。 ll mod = (ll)1e9+7; // extgcd // ax+by = gcd(a,b)の階を生成する。返り値はgcd(a…

数を加えるか、n番目に小さい値を出力して、その数を削除するか、の２つのクエリを処理するだけの問題。 簡単だけど、２分探索のところで少しバグらせてしまった。 友人曰く大事なのは highとlowどちらが合ってるのか、を理解すること。 今回だったら、lowは…

今回はgrundy数の問題。勉強したことがなかったので、蟻本を読んでから解きました。grundy数は、今の状態から一手で行ける状態のgrundy数に含まれていない最小の非負整数です。 これは、grundy数がxの状態からはgrundy数が0〜x-1の状態へ移動できる、という…