コンパクトに一般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)のような行列積で表せる。

(a,M) で互除法を走らせる。互除法の過程は mod M の上で (1,0)=...DCBA(a,M)=...DCBA(a,0) となる。...DCBAの(1,1)要素を見れば逆元が得られる。

int modinv(int a, int b=mod, int x=1, int y=0) {
	if (b==0) return x<0 ? x+mod : x;
	return modinv(b, a-a/b*b, y, x-a/b*y);
}

重心分解?

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(), 1);
		function<void(int, int)> dfs = [&](int u, int p) {
			for (int v : g[u]) if (v != p) dfs(v, u), s[u] += s[v];
		};
		function<void(int, int, int)> dfs2 = [&](int u, int p, int h) {
			parent[u] = p; head[u] = h; vid[u] = k++;
			for (int v : g[u]) if (v != p && s[u] < s[v] * 2) dfs2(v, u, h);
			for (int v : g[u]) if (v != p && s[u] >= s[v] * 2) dfs2(v, u, h);
		};
		dfs(0, -1);
		dfs2(0, -1, 0);
	}

	template<class T>
	void foreach(int u, int v, T f) {
		for (;; v = parent[v]) {
			if (vid[u] > vid[v]) swap(u, v);
			f(max(vid[u], vid[head[v]]), vid[v]);
			if (head[u] == head[v]) break;
		}
	}

	int lca(int u, int v) {
		for (; head[u] != head[v]; v = parent[head[v]]) if (vid[u] > vid[v]) swap(u, v);
		return vid[u] < vid[v] ? u : v;
	}
};

[1]ではheavy-edgeをsize[v]<size[c]*2と定義している。heavy-light decomposition という表現は見当たらないが、恐らくheavy-light decompositonの由来だろう。

[2]ではcentroid path decomposition on treeとして最大の部分木を繋ぐ辺を heavy-edge としていた。

どちらもheavy-edgeという用語を使っているため、HL分解と一括りにしても問題はない?

参考文献

[1] D. D. Sleator and R. E. Tarjan, A data structure for dynamic trees, in Proc. Thirteenth Annual ACM Symp. on Theory of Computing, 1981.
[2] Paolo Ferragina, Roberto Grossi, Ankur Gupta, Rahul Shah, Jeffrey Scott Vitter, On Searching Compressed String Collections Cache Obliviously, PODS, 2008

コンパクトに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) に基づいている(除法の原理)。mod 109+7 では再帰の深さが49以下であることを確認している。

計算量解析

雰囲気だけ書いておく。証明にはなっていないし、証明が存在するかどうかも知らない。

M%n<n/2 を満たす n の割合をコンピュータで計算してみると、約 2-log4≈0.6137 だと分かる。2-log4 の確率で値が半分になると仮定すると、再帰の深さの期待値は lg n/(2-log4) になる。実際、mod 109+7での再帰の深さの最大値が49であるのに対して期待値は48.7161なので仮定は正しそうである。よって期待計算量は O(log n) と言えそうである。