期待値= というだけの話なんですが、これしか頭にないと同じ式変形に毎回一生を費やしてしまうので典型的な用法をメモしておく。 問題： S+1の状態があり、状態0から始めて、状態Sに到達したら終了。 1回の操作で状態iから状態jに遷移する確率がのとき、終了…

というだけの話なんですが、これしか頭にないと同じ式変形に毎回一生を費やしてしまうので典型的な用法をメモしておく。記号 メビウス関数 命題Pに対してをPが真なら1、偽なら0とする（アイバーソンの記法 - Wikipedia） やりたいこと がある。を求める。 例…

writer解説が読解不可能でワロタという話を観測したので読んでみたら俺にも読解不可能でワロタ。FPSパワーを感じる学びがあったのでまとめる。出典「全ての要素がiであり、条件を満たすような長さ N の数列の個数」の母関数は になる。 したがって、「全ての…

微分方程式を微分作用素で解くやつ知ってる？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…

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

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

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

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

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