https://atcoder.jp/contests/abc189/tasks/abc189_f 概要 マス目が0からNまであるすごろくが存在していて、あなたは1からMまですべての数が等確率で出るルーレットを持っている。あなたは最初にマス0にいて、マス目Nを目指して、以下のように進む。 マス目$…

https://atcoder.jp/contests/abc191/tasks/abc191_f 概要 黒板にN個の数字${A[i]}$が書かれている。以下の操作をN-1回行って、最後に残った数は何通りあるでしょう？ 2つの数字$a, b$を選び、それらを黒板から消す。代わりに、$\min(a, b)$もしくは、$\gcd(…

https://atcoder.jp/contests/arc112/tasks/arc112_c 概要 サイズがNの根付き木が与えられる。木の根は頂点1。 AliceとBobはこの木でゲームをする。 木の各頂点には最初はすべてコインが1枚ずつ置かれている。最初に駒を用意し、頂点1(根)に置く。手番はAlic…

https://atcoder.jp/contests/abc191/tasks/abc191_d 概要 座標平面上で、$ (X, Y) $中心で半径が$ R $の円の内部や辺上に、何個の格子点(座標がすべて整数の点)がある？ 制約：$ 0 \leq |X|, |Y|, R \leq 10 ^ 5 $。$ X, Y $は小数点以下4桁まで与えられる …

https://atcoder.jp/contests/abl/tasks/abl_f 問題概要 $ 2N $人の人がいて、それぞれ身長が$ h[i] $である。 この人たちで、ペアを$ N $組作っていく。(任意の人は1つのペアにしか属してはいけない) ここで、すべてのペアのうちの2人で、お互いの身長が異…

https://atcoder.jp/contests/arc059/tasks/arc059_c 問題概要 N人の子どもがいる。それぞれ、はしゃぎ度という整数値A[i]があるとする。 この時、それぞれの子どもが飴をB[i]個もらっているとき、全体の活発度は以下のように求められる。 $$ \Pi _ {i = 1} …

この記事は、高速フーリエ変換の1つのバリエーションである、Numeric Theory Translation(数論変換)の詳しい解説記事です。 あまりなかったので書きました。 数論変換にありがちな なんで$ 10 ^ 9 + 7 $じゃダメなのか 原始根って何？ とかについてもこれを…