Doubling(ダブリング) (dp/doubling.cpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2021-03-04 00:54:11+09:00

なにこれ

各頂点からの遷移先が $1$ 点に定まっているとき，ある頂点から $T$ 回遷移したときの状態を高速に求める．

コンストラクタ

• doubling(v, _max_t)：各頂点から $1$ 回遷移した先の頂点を格納した配列 v，遷移の最大回数 _max_t を元にダブリングテーブルを構築する．
• doubling(v, v_data, _max_t, _f)：上記の引数に加え，各頂点から $1$ 回の遷移で変化する状態を格納した配列 v_data，状態遷移関数 _f を元にダブリングテーブルを構築する．

メンバ関数

• get(x, init, t)：初期頂点 x，初期値 init として t 回遷移したときの状態を返す．
• get_idx(x, t)：初期頂点 x から t 回遷移した先の頂点を返す．

計算量

頂点数を $N$，遷移回数を $T$ とし，遷移関数は $O(1)$ で動作するものとする．

• コンストラクタ：$O(N \log \max(T))$
• get(x, init, t)：$O(\log T)$
• get_idx(x, t)：$O(\log T)$

---

Verified with (AtCoder)

• abc167_d
• abc175_d

Depends on

• 2D-Array( $2$ 次元配列) (structure/2d_array.cpp)

Verified with

• test/atc_abc167_d.cpp
• test/atc_abc175_d.cpp
• test/yuki_1013.cpp
• test/yuki_1097.cpp

Code

#pragma once

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

#include "../structure/2d_array.cpp"

template<typename T = int> struct doubling {
private:
	const int n;
	const long long max_t;
	v2d<int> table;
	v2d<T> data;

	function<T(T &, T &)> f = [this](T &l, T &r) { return r; };

public:
	doubling(const vector<int> &v, long long _max_t) : n(v.size()), max_t(_max_t) {
		int k = 0;
		while((1LL << k) <= max_t) k++;
		table.assign(k, n);
		data.assign(k, n);
		table[0] = data[0] = v;

		for(int i = 0; i < k - 1; i++) {
			for(int j = 0; j < n; j++) {
				table[i + 1][j] = data[i + 1][j] = table[i][table[i][j]];
			}
		}
	}
	doubling(const vector<int> &v, const vector<T> &v_data, long long _max_t, function<T(T &, T &)> _f) :
		n(v.size()), max_t(_max_t), f(_f) {
		int k = 0;
		while((1LL << k) <= max_t) k++;
		table.assign(k, n);
		data.assign(k, n);
		table[0] = v;
		data[0] = v_data;

		for(int i = 0; i < k - 1; i++) {
			for(int j = 0; j < n; j++) {
				table[i + 1][j] = table[i][table[i][j]];
				data[i + 1][j] = f(data[i][j], data[i][table[i][j]]);
			}
		}
	}

	T get(int x, T init, long long t) {
		assert(t <= max_t);
		int id = x;
		T res = init;
		for(int k = 0; t; k++) {
			if(t & 1) {
				res = f(res, data[k][id]);
				id = table[k][id];
			}
			t >>= 1;
		}
		return res;
	}

	int get_idx(int x, long long t) {
		assert(t <= max_t);
		int id = x;
		for(int k = 0; t; k++) {
			if(t & 1) {
				id = table[k][id];
			}
			t >>= 1;
		}
		return id;
	}
};

#line 2 "dp/doubling.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

#line 2 "structure/2d_array.cpp"

#ifndef call_include
#define call_include
#include <bits/stdc++.h>
using namespace std;
#endif

template<typename T> struct v2d {
private:
	vector<vector<T>> m;

public:
	v2d() {}
	v2d(int h, int w) : m(h, vector<T>(w)) {}
	v2d(int h, int w, const T &init) : m(h, vector<T>(w, init)) {}
	v2d(const initializer_list<initializer_list<T>> m_init) : m(m_init.begin(), m_init.end()) {}

	void assign(int h, int w) {
		m.assign(h, vector<T>(w));
	}
	void assign(int h, int w, const T init) {
		m.assign(h, vector<T>(w, init));
	}

	inline int size() const {
		return m.size();
	}

	void in() {
		for(vector<T> &v : m)
			for(T &val : v) cin >> val;
	}
	void in(int h, int w) {
		m.resize(h, vector<T>(w));
		in();
	}

	void out() {
		int h = m.size();
		for(vector<T> &v : m) {
			int sz = v.size();
			for(int j = 0; j < sz; j++) {
				cout << v[j] << (j == sz - 1 ? '\n' : ' ');
			}
		}
		cout << flush;
	}

	inline vector<T> &operator[](int idx) {
		assert(0 <= idx && idx < m.size());
		return m[idx];
	}

	bool rangeout(int x, int y) {
		if(x < 0 || y < 0 || x >= size() || y >= m[x].size()) return true;
		return false;
	}
};
#line 10 "dp/doubling.cpp"

template<typename T = int> struct doubling {
private:
	const int n;
	const long long max_t;
	v2d<int> table;
	v2d<T> data;

	function<T(T &, T &)> f = [this](T &l, T &r) { return r; };

public:
	doubling(const vector<int> &v, long long _max_t) : n(v.size()), max_t(_max_t) {
		int k = 0;
		while((1LL << k) <= max_t) k++;
		table.assign(k, n);
		data.assign(k, n);
		table[0] = data[0] = v;

		for(int i = 0; i < k - 1; i++) {
			for(int j = 0; j < n; j++) {
				table[i + 1][j] = data[i + 1][j] = table[i][table[i][j]];
			}
		}
	}
	doubling(const vector<int> &v, const vector<T> &v_data, long long _max_t, function<T(T &, T &)> _f) :
		n(v.size()), max_t(_max_t), f(_f) {
		int k = 0;
		while((1LL << k) <= max_t) k++;
		table.assign(k, n);
		data.assign(k, n);
		table[0] = v;
		data[0] = v_data;

		for(int i = 0; i < k - 1; i++) {
			for(int j = 0; j < n; j++) {
				table[i + 1][j] = table[i][table[i][j]];
				data[i + 1][j] = f(data[i][j], data[i][table[i][j]]);
			}
		}
	}

	T get(int x, T init, long long t) {
		assert(t <= max_t);
		int id = x;
		T res = init;
		for(int k = 0; t; k++) {
			if(t & 1) {
				res = f(res, data[k][id]);
				id = table[k][id];
			}
			t >>= 1;
		}
		return res;
	}

	int get_idx(int x, long long t) {
		assert(t <= max_t);
		int id = x;
		for(int k = 0; t; k++) {
			if(t & 1) {
				id = table[k][id];
			}
			t >>= 1;
		}
		return id;
	}
};

Back to top page