naoya_t@hatenablog

いわゆるチラシノウラであります

Mathematics

期待値の線形性(が腑に落ちるまでの長い軌跡)

「期待値の線形性」について、けんちょん先生やふるやん先生の解説を参考にしながら自分の理解を整理するためのメモ。 期待値の線形性そのもの E[ax+b]=aE[x]+E[b] は分かってるし、「E[Σf(x)]の形で書けるものはΣE[f(x)]に書き換えて解ける」という事実にも…

高速ゼータ変換/高速メビウス変換

ゼータ変換/メビウス変換は互いに逆変換の関係なのはわかったんだけど…どっちがどっち?というか、4種類あるんだけど…どれがどれ?(けんちょん先生が全ての謎を解いてくれるのを待ちつつ)

MathMash Round 19

6/11 2:25-4:25am JST ABCの後に寝落ちして、ちょうど目が覚めたところでTLで目に飛び込んできたので(急遽アカウントを作って)出てみた 7完 (ABCDEF-H) 9816点で8位 1248(+248) EとHはズルしてる

DFT(離散フーリエ変換)とNTT(数論変換:整数(剰余環)を用いたDFT)

先日ARC埋めの一環でATC001のC問題(高速フーリエ変換)を解いたのだけれど、こういう畳み込み問題はDFT(discrete Fourier transform;離散フーリエ変換)の代わりに NTT(number-theoretical transform;数論変換)という "整数(剰余環)を用いたDFT" で…

拡張ユークリッド互除法の話

先日の連分数の計算と拡張ユークリッド互除法って少し似てるなと思ったというメモ。(連分数の計算で次の項を求める時にやっている操作ってユークリッドの互除法そのものだし当然か)拡張ユークリッド互除法というのは、 を満たす を求める方法。 を で割れば…

連分数 (continued fraction)

連分数 - WipikediaこないだのJune Long ChallengeのEuler Sumを考えてる時に Mark Jason Dominus氏のスライド Arithmetic with Continued Fractions を読んだ時のメモ。連分数とかいじるのって多分昔SICPを読んだ時以来。