メモ

yukicoderでゆるふわgolf

テクニック

線形漸化式と微分方程式

微分方程式を微分作用素で解くやつ知ってる?f''-3f'+2f=0 の解は? 微分作用素をDとして、与えられた方程式は(D-1)(D-2)f=0 ここで一般に(D-k)f=0の解はC*e^kxなので、f(x)=C1*e^x+C2*e^2x全く同じようにして線形漸化式の一般項が出るんですよねa[n+2]-3a[n…

sum of multiplicative function

これはなに?Min_25さんの以下の記事を自分が読みやすいように書き換えたものです。 min-25.hatenablog.com Min_25さんによる実装はこちら https://ideone.com/9F9amv 要求知識 ・平方根の上下で分けるテク ・fenwick tree ・線形篩の"気持ち"を知っていると…

指数型母関数

この記事は 37zigenさんによる以下の記事をもとに、お気持ちパートを自分にとってわかりやすいようにメモしたものです。 真面目な解説は書いていないので、そういうのを読みたい人は元記事の方をみてください。 37zigen.com ・物を数える気持ち:「互いに区…

FFT

何回見ても非再帰FFTの話が覚えられないのでメモ1のN乗根をgとする。 をFFTしたい。 その結果は になる。ということで、全てのiについての が求められればよい。 これを頑張って計算する。 ところで、再帰FFTの気持ちには2種類あることをご存じでしたか?ぼ…

遅延セグメント木

この記事では遅延セグメント木の「気持ち」を説明します。 通常のセグメント木に関する知識を前提とします。 アルゴリズムの説明のみであり、実装については一切説明していません。 基本的には以下のサイトの記述を、自分好みにリライトしたものです。 beet-…

Berlekamp–Massey algorithm

この記事ではBerlekamp–Massey algorithmの「気持ち」を形式的べき級数(母関数)を用いて説明します。 (日本語で詳しく説明しているサイトが見つからなかったので) 間違った説明はしていないつもりですが、(故意に)不正確な記述があるかもしれません。 …