This documentation is automatically generated by competitive-verifier/competitive-verifier
各頂点からの遷移先が $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)$ で動作するものとする.
get(x, init, t)
:$O(\log T)$get_idx(x, t)
:$O(\log T)$#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;
}
};