小ネタ

コンパクトに一般modの逆元を求める

ユークリッドの互除法は (a,b)->(b,a-floor(a/b)*b) という変換を繰り返すアルゴリズムである。この変換は行列 A={{0,1},{1,-floor(a/b)}}を用いて (a',b')=A(a,b)と書ける。これを繰り返し行うため、互除法の過程は(1,0)=...DCBA(a,b)のような行列積で表せ…

重心分解?

2017/08/02(修正) HL分解と重心分解の定義を誤解してた?HL分解:size[v]<size[c]*2の辺を選択 重心分解:argmax size[c]の辺を選択いままで重心分解で書いてたけど、HL分解の方が実装が楽?(重心分解はmaxの更新が面倒だと思う)。 struct HLD { vector<int> parent, head, vid; HLD(const vector<vector<int>> &g) : parent(g.size()), head(g.size()), vid(g.size()) { int k = 0; vector<int> s(g.size(),…</int></vector<int></size[c]*2の辺を選択>

コンパクトにmod逆元を求める

mod逆元を求めたいだけなのに繰り返し二乗法を書くのは面倒。そういうときに使える手法。素数mod限定。 long long modinv(long long n) { return n == 1 ? n : modinv(MOD % n) * (MOD - MOD / n) % MOD; } 上の計算式は M%n+⌊M/n⌋n=M≡0 (mod M) に基づいて…

prime counting function

以下の問題を解く際に「n 以下の素数の個数」を高速に求める必要が出てくる。http://codeforces.com/contest/665/problem/F素数列を\(p_0,p_1,\ldots\)とする。\(\phi(x,p_i)\)を\(x\)以下の正整数のうち\(p_0,p_1,\ldots,p_i\)を約数に持たないものの個数と…

右方向の和を求めるBIT

本当にどうでもいい内容です。以下のように書けば sum(a[0..k]) が求められます。1-indexedのBITを0-indexedとして使うために最初にk++しています。 const int N = 1e5; int bit[N + 1]; void bitadd(int k, int v) { for (k++; k <= N; k += k & -k) { bit[…