{ // Place your snippets for cpp here. Each snippet is defined under a snippet name and has a prefix, body and // description. The prefix is what is used to trigger the snippet and the body will be expanded and inserted. Possible variables are: // $1, $2 for tab stops, $0 for the final cursor position, and ${1:label}, ${2:another} for placeholders. Placeholders with the // same ids are connected. // Example: // "Print to console": { // "prefix": "log", // "body": [ // "console.log('$1');", // "$2" // ], // "description": "Log output to console" // } "template": { "prefix": "atcoder_cpp_", "body": [ "#include ", "#include ", "using namespace std;", "using namespace atcoder;", "istream &operator>>(istream &is, modint &a) { long long v; is >> v; a = v; return is; }", "ostream &operator<<(ostream &os, const modint &a) { return os << a.val(); }", "istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; }", "ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); }", "istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; }", "ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); } ", "", "typedef long long ll;", "typedef vector> Graph;", "typedef pair pii;", "typedef pair pll;", "#define FOR(i,l,r) for (int i = l;i < (int)(r); i++)", "#define rep(i,n) for (int i = 0;i < (int)(n); i++)", "#define all(x) x.begin(), x.end()", "#define rall(x) x.rbegin(), x.rend()", "#define my_sort(x) sort(x.begin(), x.end())", "#define my_max(x) *max_element(all(x))", "#define my_min(x) *min_element(all(x))", "template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }", "template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }", "const int INF = (1<<30) - 1;", "const ll LINF = (1LL<<62) - 1;", "const int MOD = 998244353;", "const int MOD2 = 1e9+7;", "const double PI = acos(-1);", "vector di = {1,0,-1,0};", "vector dj = {0,1,0,-1};", "", "#ifdef LOCAL", "# include ", "# define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)", "#else", "# define debug(...) (static_cast(0))", "#endif", "", "int main(){", " cin.tie(0);", " ios_base::sync_with_stdio(false);", "}", "" ], "description": "template" }, "codeforces": { "prefix": "atcoder_cpp_codeforces", "body": [ "#include ", "using namespace std;", "", "typedef long long ll;", "typedef vector> Graph;", "typedef pair pii;", "typedef pair pll;", "#define FOR(i,l,r) for (int i = l;i < (int)(r); i++)", "#define rep(i,n) for (int i = 0;i < (int)(n); i++)", "#define all(x) x.begin(), x.end()", "#define rall(x) x.rbegin(), x.rend()", "#define my_sort(x) sort(x.begin(), x.end())", "#define my_max(x) *max_element(all(x))", "#define my_min(x) *min_element(all(x))", "template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }", "template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }", "const int INF = (1<<30) - 1;", "const ll LINF = (1LL<<62) - 1;", "const int MOD = 998244353;", "const int MOD2 = 1e9+7;", "const double PI = acos(-1);", "vector di = {1,0,-1,0};", "vector dj = {0,1,0,-1};", "", "#ifdef LOCAL", "# include ", "# define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)", "#else", "# define debug(...) (static_cast(0))", "#endif", "", "void solve(){", "}", "", "int main(){", " cin.tie(0);", " ios_base::sync_with_stdio(false);", " int t = 1; ", " cin >> t;", " while(t--) solve();", "}" ], "description": "codeforces" }, // //data structure // "sortedset": { "prefix": "atcoder_data_sortedset", "body": [ "template", "struct SortedSet{", " const int BUCKET_RATIO = 50;", " const int SPLIT_RATIO = 170;", " vector> a;", " int sz = 0;", "", " SortedSet(){}", " SortedSet(const vector &vec){", " vector dat = vec;", " sort(dat.begin(), dat.end());", " dat.erase(unique(dat.begin(), dat.end()), dat.end());", "", " int n = sz = dat.size();", " int num_bucket = (int)ceil(sqrt((double)n / (double)BUCKET_RATIO));", " a.resize(num_bucket);", " for(int i = 0; i < num_bucket; i++){", " a[i] = vector(dat.begin() + n * i / num_bucket, dat.begin() + n * (i + 1) / num_bucket);", " }", " }", "", " bool operator==(const SortedSet& other) {", " return this->a == other.a;", " }", "", " size_t size() { return sz; }", "", " friend ostream& operator<<(ostream& os, const SortedSet& st) {", " os << \"{ \";", " for(const auto&vec : st.a){", " for(const auto& v : vec){", " os << v << \" \";", " }", " }", " os << \"}\";", " return os;", " }", "", " pair _position(const T &x){", " int as = a.size();", " for(int i = 0; i < as; i++){", " if(x <= a[i].back()) {", " return make_pair(i, lower_bound(a[i].begin(), a[i].end(), x) - a[i].begin());", " }", " }", " return make_pair(as - 1, lower_bound(a[as - 1].begin(), a[as - 1].end(), x) - a[as - 1].begin());", " }", "", " int count(const T &x){ return this->index_right(x) - this->index(x); }", "", " bool add(const T &x){", " if(sz == 0){", " a = {{x}};", " sz = 1;", " return true;", " }", " auto [b, i] = _position(x);", " if(i != (int)a[b].size() && a[b][i] == x) return false;", " a[b].insert(a[b].begin() + i, x);", " sz++;", " if((int)a[b].size() > (int)a.size() * SPLIT_RATIO){", " int mid = (int)a[b].size() >> 1;", " vector head(a[b].begin(), a[b].begin() + mid), tail(a[b].begin() + mid, a[b].end());", " a.erase(a.begin() + b);", " a.insert(a.begin() + b, tail);", " a.insert(a.begin() + b, head);", " }", " return true;", " }", "", " T _pop(int b, int i){", " T ans = a[b][i];", " a[b].erase(a[b].begin() + i);", " sz--;", " if((int)a[b].size() == 0) a.erase(a.begin() + b);", " return ans;", " }", " ", " bool discard(const T &x){", " if(sz == 0) return false;", " auto [b, i] = _position(x);", " if(i == (int)a[b].size() || a[b][i] != x) return false;", " _pop(b, i);", " return true;", " }", "", " optional lt(const T &x){", " for(int b = (int)a.size() - 1; b >= 0; b--){", " if(a[b][0] < x){", " int l = lower_bound(a[b].begin(), a[b].end(), x) - a[b].begin();", " return a[b][l - 1];", " }", " }", " return nullopt;", " }", "", " optional le(const T &x){", " for(int b = (int)a.size() - 1; b >= 0; b--){", " if(a[b][0] <= x){", " int r = upper_bound(a[b].begin(), a[b].end(), x) - a[b].begin();", " return a[b][r - 1];", " }", " }", " return nullopt;", " }", "", " optional gt(const T &x){", " for(int b = 0; b < (int)a.size(); b++){", " if(a[b].back() > x){", " int r = upper_bound(a[b].begin(), a[b].end(), x) - a[b].begin();", " return a[b][r];", " }", " }", " return nullopt;", " }", "", " optional ge(const T &x){", " for(int b = 0; b < (int)a.size(); b++){", " if(a[b].back() >= x){", " int l = lower_bound(a[b].begin(), a[b].end(), x) - a[b].begin();", " return a[b][l];", " }", " }", " return nullopt;", " }", "", " const T& operator[](int i) const {", " if(i < 0){", " assert(~i < sz);", " for(int b = (int)a.size() - 1; b >= 0; b--){", " i += (int)a[b].size();", " if (i >= 0) return a[b][i];", " }", " }", " else{", " assert(i < sz);", " for(int b = 0; b < (int)a.size(); b++){", " if(i < (int)a[b].size()) return a[b][i];", " i -= (int)a[b].size();", " }", " }", " }", "", " T pop(int i){", " if(i < 0){", " assert(~i < sz);", " for(int b = (int)a.size() - 1; b >= 0; b--){", " i += (int)a[b].size();", " if (i >= 0) return _pop(b, i);", " }", " }", " else{", " assert(i < sz);", " for(int b = 0; b < (int)a.size(); b++){", " if(i < (int)a[b].size()) return _pop(b, i);", " i -= (int)a[b].size();", " }", " }", " }", "", " int index(const T &x){", " int ans = 0;", " for(int b = 0; b < (int)a.size(); b++){", " if(a[b].back() >= x){", " return ans + lower_bound(a[b].begin(), a[b].end(), x) - a[b].begin();", " }", " ans += (int)a[b].size();", " }", " return ans;", " }", "", " int index_right(const T &x){", " int ans = 0;", " for(int b = 0; b < (int)a.size(); b++){", " if(a[b].back() > x){", " return ans + upper_bound(a[b].begin(), a[b].end(), x) - a[b].begin();", " }", " ans += (int)a[b].size();", " }", " return ans;", " }", "};", "", "template", "struct SortedMultiSet{", " const int BUCKET_RATIO = 50;", " const int SPLIT_RATIO = 170;", " vector> a;", " int sz = 0;", "", " SortedMultiSet(){}", " SortedMultiSet(const vector &vec){", " vector dat = vec;", " sort(dat.begin(), dat.end());", "", " int n = sz = dat.size();", " int num_bucket = (int)ceil(sqrt((double)n / (double)BUCKET_RATIO));", " a.resize(num_bucket);", " for(int i = 0; i < num_bucket; i++){", " a[i] = vector(dat.begin() + n * i / num_bucket, dat.begin() + n * (i + 1) / num_bucket);", " }", " }", "", " bool operator==(const SortedMultiSet& other) {", " return this->a == other.a;", " }", "", " size_t size() { return sz; }", "", " friend ostream& operator<<(ostream& os, const SortedMultiSet& st) {", " os << \"{ \";", " for(const auto&vec : st.a){", " for(const auto& v : vec){", " os << v << \" \";", " }", " }", " os << \"}\";", " return os;", " }", "", " pair _position(const T &x){", " int as = a.size();", " for(int i = 0; i < as; i++){", " if(x <= a[i].back()) {", " return make_pair(i, lower_bound(a[i].begin(), a[i].end(), x) - a[i].begin());", " }", " }", " return make_pair(as - 1, lower_bound(a[as - 1].begin(), a[as - 1].end(), x) - a[as - 1].begin());", " }", "", " int count(const T &x) { return this->index_right(x) - this->index(x); }", "", " void add(const T &x){", " if(sz == 0){", " a = {{x}};", " sz = 1;", " return;", " }", " auto [b, i] = _position(x);", " a[b].insert(a[b].begin() + i, x);", " sz++;", " if((int)a[b].size() > (int)a.size() * SPLIT_RATIO){", " int mid = (int)a[b].size() >> 1;", " vector head(a[b].begin(), a[b].begin() + mid), tail(a[b].begin() + mid, a[b].end());", " a.erase(a.begin() + b);", " a.insert(a.begin() + b, tail);", " a.insert(a.begin() + b, head);", " }", " }", "", " T _pop(int b, int i){", " T ans = a[b][i];", " a[b].erase(a[b].begin() + i);", " sz--;", " if((int)a[b].size() == 0) a.erase(a.begin() + b);", " return ans;", " }", " ", " bool discard(const T &x){", " if(sz == 0) return false;", " auto [b, i] = _position(x);", " if(i == (int)a[b].size() || a[b][i] != x) return false;", " _pop(b, i);", " return true;", " }", "", " optional lt(const T &x){", " for(int b = (int)a.size() - 1; b >= 0; b--){", " if(a[b][0] < x){", " int l = lower_bound(a[b].begin(), a[b].end(), x) - a[b].begin();", " return a[b][l - 1];", " }", " }", " return nullopt;", " }", "", " optional le(const T &x){", " for(int b = (int)a.size() - 1; b >= 0; b--){", " if(a[b][0] <= x){", " int r = upper_bound(a[b].begin(), a[b].end(), x) - a[b].begin();", " return a[b][r - 1];", " }", " }", " return nullopt;", " }", "", " optional gt(const T &x){", " for(int b = 0; b < (int)a.size(); b++){", " if(a[b].back() > x){", " int r = upper_bound(a[b].begin(), a[b].end(), x) - a[b].begin();", " return a[b][r];", " }", " }", " return nullopt;", " }", "", " optional ge(const T &x){", " for(int b = 0; b < (int)a.size(); b++){", " if(a[b].back() >= x){", " int l = lower_bound(a[b].begin(), a[b].end(), x) - a[b].begin();", " return a[b][l];", " }", " }", " return nullopt;", " }", "", " const T& operator[](int i) const {", " if(i < 0){", " assert(~i < sz);", " for(int b = (int)a.size() - 1; b >= 0; b--){", " i += (int)a[b].size();", " if (i >= 0) return a[b][i];", " }", " }", " else{", " assert(i < sz);", " for(int b = 0; b < (int)a.size(); b++){", " if(i < (int)a[b].size()) return a[b][i];", " i -= (int)a[b].size();", " }", " }", " }", "", " T pop(int i){", " if(i < 0){", " assert(~i < sz);", " for(int b = (int)a.size() - 1; b >= 0; b--){", " i += (int)a[b].size();", " if (i >= 0) return _pop(b, i);", " }", " }", " else{", " assert(i < sz);", " for(int b = 0; b < (int)a.size(); b++){", " if(i < (int)a[b].size()) return _pop(b, i);", " i -= (int)a[b].size();", " }", " }", " }", "", " int index(const T &x){", " int ans = 0;", " for(int b = 0; b < (int)a.size(); b++){", " if(a[b].back() >= x){", " return ans + lower_bound(a[b].begin(), a[b].end(), x) - a[b].begin();", " }", " ans += (int)a[b].size();", " }", " return ans;", " }", "", " int index_right(const T &x){", " int ans = 0;", " for(int b = 0; b < (int)a.size(); b++){", " if(a[b].back() > x){", " return ans + upper_bound(a[b].begin(), a[b].end(), x) - a[b].begin();", " }", " ans += (int)a[b].size();", " }", " return ans;", " }", "};", "" ], "description": "sortedset" }, "removable_pq": { "prefix": "atcoder_data_removable_pq", "body": [ "struct T{", " int rate;", " T(int _rate) : rate(_rate) {}", "", " bool operator<(const T& x) const {", " return this->rate < x.rate;", " }", "", " bool operator==(const T& x) const {", " return this->rate == x.rate;", " }", "};", "", "// you cannot erase element not in Q;", "// only greater", "template ", "struct removable_priority_queue{", " priority_queue Q, R;", " removable_priority_queue(){}", "", " void push(T x){ Q.push(x); }", "", " void erase(T x){ R.push(x); }", "", " T top(){", " assert(!this->empty());", " while(!R.empty() && R.top() == Q.top()){", " R.pop();", " Q.pop();", " }", " return Q.top();", " };", "", " int size(){ return Q.size() - R.size(); }", "", " bool empty(){ return size() == 0; }", "};", "" ], "description": "removable_pq" }, "RAQRSQ": { "prefix": "atcoder_data_RAQRSQ", "body": [ "// verify : https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=9516360#1", "template", "struct RangeAddRangeSum{", " int n;", " atcoder::fenwick_tree fw0, fw1;", " RangeAddRangeSum(int n) : n(n) {", " fw0 = atcoder::fenwick_tree(n + 1);", " fw1 = atcoder::fenwick_tree(n + 1);", " }", "", " void add(int l, int r, T x){", " fw0.add(l, -x * (T)(l - 1));", " fw0.add(r, x * (T)(r - 1));", " fw1.add(l, x);", " fw1.add(r, -x);", " }", "", " void add(int i, T x) { return add(i, i + 1, x); }", "", " // [0, i)", " T _sum(int i) { return fw0.sum(0, i) + fw1.sum(0, i) * (T)(i - 1); }", "", " // [l, r)", " T sum(int l, int r) { return _sum(r) - _sum(l); }", "};", "" ], "description": "RAQRSQ" }, "sparsetable2d": { "prefix": "atcoder_data_sparsetable2d", "body": [ "template", "struct SparseTable2d{", " vector>>> table;", " vector bit_len; // bit_len[i] ... iを超えない最大の指数 (ex bit_len[6] = 2)", " SparseTable2d(vector> &vec){", " _build(vec);", " }", "", " void _build(vector> &vec){", " int H = vec.size(), W = vec[0].size();", " int logH = 0, logW = 0;", " while((1 << logH) <= H) logH++;", " while((1 << logW) <= W) logW++;", "", " table.resize(logH, vector(logW, vector((1 << logH), vector((1 << logW), e()))));", " for(int i = 0; i < H; i++){", " for(int j = 0; j < W; j++){", " table[0][0][i][j] = vec[i][j];", " }", " }", "", " for(int k = 0; k + 1 < logH; k++){", " for(int i = 0; i + (1 << k) < (1 << logH); i++){", " for(int j = 0; j < (1 << logW); j++){", " table[k + 1][0][i][j] = op(table[k][0][i][j], table[k][0][i + (1 << k)][j]);", " }", " }", " }", "", " for(int k = 0; k < logH; k++){", " for(int l = 0; l + 1 < logW; l++){", " for(int i = 0; i + (1 << k) < (1 << logH); i++){", " for(int j = 0; j + (1 << l) < (1 << logW); j++){", " table[k][l + 1][i][j] = op(table[k][l][i][j], table[k][l][i][j + (1 << l)]);", " }", " }", " }", " }", "", " bit_len.resize(max(H, W) + 1, 0);", " for(int i = 2; i < (int)bit_len.size(); i++){", " bit_len[i] = bit_len[i >> 1] + 1;", " }", " }", "", " // [i0, i1) x [j0, j1)", " S prod(int i0, int i1, int j0, int j1){", " if(i0 >= i1 || j0 >= j1) return e();", " int bi = bit_len[i1 - i0];", " int bj = bit_len[j1 - j0];", " return op(", " op(table[bi][bj][i0][j0], table[bi][bj][i1 - (1 << bi)][j0]),", " op(table[bi][bj][i0][j1 - (1 << bj)], table[bi][bj][i1 - (1 << bi)][j1 - (1 << bj)])", " );", " }", "};", "" ], "description": "sparsetable2d" }, "sparsetable": { "prefix": "atcoder_data_sparsetable", "body": [ "template ", "struct SparseTable {", " vector> table;", " vector bit_len; // bit_len[i] ... iを超えない最大の指数 (ex bit_len[6] = 2)", " SparseTable(vector &vec){ ", " _build(vec);", " }", "", " void _build(vector &vec){", " int N = vec.size();", " int logN = 0;", " while((1 << logN) <= N)logN++;", "", " table.resize(logN, vector(1 << logN, e()));", " for(int i = 0; i < N; i++){", " table[0][i] = vec[i];", " }", " for(int i = 0; i + 1 < logN; i++){", " for(int j = 0; j + (1 << i) < (1 << logN); j++){", " table[i + 1][j] = op(table[i][j], table[i][j + (1 << i)]);", " }", " }", " bit_len.resize(N + 1, 0);", " for(int i = 2; i < (int)bit_len.size(); i++){", " bit_len[i] = bit_len[i >> 1] + 1;", " }", " }", "", " S get(int p){", " return table[0][p];", " }", "", " S prod(int l, int r){", " if (r - l <= 0) return e();", " int b = bit_len[r - l];", " return op(table[b][l], table[b][r - (1 << b)]);", " }", "};", "" ], "description": "sparsetable" }, "rangetree": { "prefix": "atcoder_data_rangetree", "body": [ "", "template struct RangeTree {", " using CT = CoordinateType;", " using Point = pair;", " vector points;", " vector> yx;", " vector> seg;", " int n;", "", " void _set(int idx, Point p, S val){", " int i = lower_bound(yx[idx].begin(), yx[idx].end(), Point{p.second, p.first}) - yx[idx].begin();", " seg[idx].set(i, val);", " }", " S _prod(int idx, CT yl, CT yr){", " auto comp = [](const Point &lhs, const Point &rhs) {return lhs.first < rhs.first; };", " int il = lower_bound(yx[idx].begin(), yx[idx].end(), Point{yl, yl}, comp) - yx[idx].begin();", " int ir = lower_bound(yx[idx].begin(), yx[idx].end(), Point{yr, yr}, comp) - yx[idx].begin();", " return seg[idx].prod(il, ir);", " }", "", " void add_point(CT x, CT y){", " points.push_back(Point{x, y});", " }", "", " void build(){", " sort(points.begin(), points.end());", " points.erase(unique(points.begin(), points.end()), points.end());", " n = points.size();", "", " yx.resize(2 * n);", " for(int i = 0; i < n; i++) yx[i + n] = { Point{points[i].second, points[i].first}};", " for(int i = n - 1; i > 0; i--){", " auto &lc = yx[2 * i];", " auto &rc = yx[2 * i + 1];", " merge(lc.begin(), lc.end(), rc.begin(), rc.end(), back_inserter(yx[i]));", " yx[i].erase(unique(yx[i].begin(), yx[i].end()), yx[i].end());", " }", " for(const auto &v : yx) seg.emplace_back(v.size());", " }", "", " void set(CT x, CT y, S val){", " int i = lower_bound(points.begin(), points.end(), Point{x, y}) - points.begin() + n;", " while(i){", " _set(i, Point{x, y}, val);", " i = i >> 1;", " }", " }", "", " S prod(CT xl, CT xr, CT yl, CT yr){", " auto comp = [](const Point &lhs, const Point &rhs) {return lhs.first < rhs.first; };", " int l = lower_bound(points.begin(), points.end(), Point{xl, yr}, comp) - points.begin() + n;", " int r = lower_bound(points.begin(), points.end(), Point{xr, yr}, comp) - points.begin() + n;", " S sml = e(), smr = e();", " while(l < r){", " if(l & 1) sml = op(sml, _prod(l++, yl, yr));", " if(r & 1) smr = op(_prod(--r, yl, yr), smr);", " l >>= 1;", " r >>= 1;", " }", "", " return op(sml, smr);", " }", "", " S get(CT x, CT y){", " return prod(x, x + 1, y, y + 1);", " }", "};" ], "description": "rangetree" }, "compress": { "prefix": "atcoder_data_compress", "body": [ "template", "struct Compress{", " vector res;", " map org_2_comp;", " map comp_2_org;", " Compress(vector &vec, int base=0){init(vec,base);};", " void init(vector &vec, int base=0){", " int N = vec.size();", " res.assign(N,-1);", " int cnt = base;", " set st;", " for(int i=0;i get_comp(){", " return res;", " }", " // 元の値->座圧した値", " int org2comp(T &val){", " return org_2_comp[val];", " }", " // 座圧した値->元の値", " T comp2org(int &idx){", " return comp_2_org[idx];", " }", "};", "", "template", "struct Compress_multi{ // 同じ値を別に考える", " vector res;", " map org_2_min_comp, org_2_max_comp;", " map comp_2_org;", " Compress_multi(vector &vec, int base=0){init(vec,base);};", " void init(vector &vec, int base=0){", " int N = vec.size();", " res.assign(N,-1);", " int cnt = base;", " vector> val_and_idx(N);", " rep(i,N) val_and_idx[i] = make_pair(vec[i], i);", " sort(all(val_and_idx));", " rep(i,N) {", " T val = val_and_idx[i].first;", " int idx = val_and_idx[i].second;", " if (!org_2_min_comp.count(val)) org_2_min_comp[val] = cnt;", " if (!org_2_max_comp.count(val)) org_2_max_comp[val] = cnt;", " chmax(org_2_max_comp[val],cnt);", " res[idx] = cnt;", " comp_2_org[cnt] = val;", " cnt++;", " }", " }", " // 座圧した値を返す", " int get(int idx){", " return res[idx];", " }", " // 座圧したリストを返す", " vector get_comp(){", " return res;", " }", " // 座圧した値->元の値", " T comp2org(int &idx){", " return comp_2_org[idx];", " }", " // 元の値->座圧した値で最小", " int org2comp_min(T &val){", " return org_2_min_comp[val];", " }", " // 元の値->座圧した値で最大", " int org2comp_max(T &val){", " return org_2_max_comp[val];", " }", "};", "" ], "description": "compress" }, "cumulate": { "prefix": "atcoder_data_cumulate2d", "body": [ "struct cumulative_sum_2d{", " int H,W;", " vector> val;", " vector> wa;", " cumulative_sum_2d(int H_input, int W_input){init(H_input,W_input);}", " void init(int H_input, int W_input){", " H = H_input;", " W = W_input;", " val.assign(H,vector(W,0ll));", " wa.assign(H+1,vector(W+1,0ll));", " }", " void set(int i, int j, ll value){", " val[i][j] = value;", " }", " void add(int i, int j, ll value){", " val[i][j] += value;", " }", " void build(){", " for(int i=0;i> imos;", " imos_2d(int H_input, int W_input){init(H_input, W_input);}", " void init(int H_input, int W_input){", " H = H_input;", " W = W_input;", " imos.assign(H+1,vector(W+1,0ll));", " }", " //[i1,i2)x[i2,j2)の長方形にvalを足す", " void add(int i1, int j1, int i2, int j2, int val){", " imos[i1][j1] += val;", " imos[i2][j1] -= val;", " imos[i1][j2] -= val;", " imos[i2][j2] += val;", " }", " void build(){", " for(int i=0;i<=H;i++){", " for(int j=0;j,greater> min_hq;", " priority_queue> max_hq;", " map mp; // {value, count}", " ll _size = 0;", " ll _total = 0;", " DoubleHeap(){}", " //", " ll count(ll x){", " return mp[x];", " }", " //", " ll size(){", " return _size;", " }", " //", " ll sum(){", " return _total;", " }", " //", " void insert(ll x){", " _size++;", " _total += x;", " min_hq.push(x);", " max_hq.push(x);", " mp[x]++;", " }", " // 削除した個数を返す", " ll erase(ll x, ll n = LINF){", " if (count(x) < n) n = count(x);", " _size -= n;", " _total -= n * x;", " mp[x] -= n;", " // if(mp[x]==0) mp.erase(x);", " while((!min_hq.empty()) && (count(min_hq.top()) == 0)) min_hq.pop();", " while((!max_hq.empty()) && (count(max_hq.top()) == 0)) max_hq.pop();", " return n;", " }", " // ", " void discard(ll x){", " erase(x, 1);", " }", " // ", " ll get_min(){", " return min_hq.top();", " };", " //", " ll get_max(){", " return max_hq.top();", " };", " //", " ll pop_min(){", " ll v = get_min();", " discard(v);", " return v;", " }", " //", " ll pop_max(){", " ll v = get_max();", " discard(v);", " return v;", " }", " ", " // debug", " vector> dump(){", " vector> res; // (value, cnt)", " for(auto itr = mp.begin(); itr != mp.end(); itr++){", " res.push_back(make_pair(itr->first, itr->second));", " }", " return res;", " }", "};", "" ], "description": "doubleheap" }, "swag": { "prefix": "atcoder_data_swag", "body": [ "//https://qiita.com/Shirotsume/items/4a2837b5895ef9a7aeb1#foldable-stack-%E3%81%AB%E3%81%A4%E3%81%84%E3%81%A6", "template ", "struct SWAG {", " vector top, bottom, topfold, bottomfold;", " SWAG(){", " topfold.push_back(e());", " bottomfold.push_back(e());", " }", " void _pushbottom(T x){", " bottom.push_back(x);", " bottomfold.push_back(op(bottomfold.back(), x));", " }", " T _popbottom(){", " auto res = bottom.back();", " bottom.pop_back();", " bottomfold.pop_back();", " return res;", " }", " void _pushtop(T x){", " top.push_back(x);", " topfold.push_back(op(x, topfold.back()));", " }", " T _poptop(){", " auto res = top.back();", " top.pop_back();", " topfold.pop_back();", " return res;", " }", " void push(T x){", " _pushbottom(x);", " }", " void pushleft(T x){", " _pushtop(x);", " }", " T fold(){", " return op(topfold.back(), bottomfold.back());", " }", " T popleft(){", " if (top.empty()){", " vector stack_;", " while(!bottom.empty()){", " auto x = _popbottom();", " stack_.push_back(x);", " }", " int N = stack_.size();", " reverse(all(stack_));", " vector stack1, stack2;", " for(int i=0;i stack_;", " while(!top.empty()){", " auto x = _poptop();", " stack_.push_back(x);", " }", " int N = stack_.size();", " vector stack1, stack2;", " for(int i=0;i sw;", "" ], "description": "swag" }, "BinaryTrie": { "prefix": "atcoder_data_binary_trie", "body": [ "// Binary Trie", "template struct BinaryTrie {", " struct Node {", " size_t count;", " Node *prev, *left, *right;", " Node(Node *prev) : count(0), prev(prev), left(nullptr), right(nullptr) {}", " };", " INT lazy;", " Node *root;", "", " // constructor", " BinaryTrie() : lazy(0), root(emplace(nullptr)) {}", " inline size_t get_count(Node *v) const { return v ? v->count : 0; }", "", " // add and get value of Node", " inline void add(INT val) {", " lazy ^= val;", " }", " inline INT get(Node *v) {", " if (!v) return -1;", " INT res = 0;", " for (int i = 0; i < MAX_DIGIT; ++i) {", " if (v == v->prev->right)", " res |= INT(1)<prev;", " }", " return res ^ lazy;", " }", "", " // find Node* whose value is val", " Node* find(INT val) {", " INT nval = val ^ lazy;", " Node *v = root;", " for (int i = MAX_DIGIT-1; i >= 0; --i) {", " bool flag = (nval >> i) & 1;", " if (flag) v = v->right;", " else v = v->left;", " if (!v) return v;", " }", " return v;", " }", "", " // insert", " inline Node* emplace(Node *prev) {", " return new Node(prev);", " }", " void insert(INT val, size_t k = 1) {", " INT nval = val ^ lazy;", " Node *v = root;", " for (int i = MAX_DIGIT-1; i >= 0; --i) {", " bool flag = (nval >> i) & 1;", " if (flag && !v->right) v->right = emplace(v);", " if (!flag && !v->left) v->left = emplace(v);", " if (flag) v = v->right;", " else v = v->left;", " }", " v->count += k;", " while ((v = v->prev)) v->count = get_count(v->left) + get_count(v->right);", " }", " ", " // erase", " Node* clear(Node *v) {", " if (!v || get_count(v)) return v;", " delete(v);", " return nullptr;", " }", " bool erase(Node *v, size_t k = 1) {", " if (!v) return false;", " v->count -= k;", " while ((v = v->prev)) {", " v->left = clear(v->left);", " v->right = clear(v->right);", " v->count = get_count(v->left) + get_count(v->right);", " }", " return true;", " }", " bool erase(INT val) {", " auto v = find(val);", " return erase(v);", " }", " bool erase_k(INT val, size_t k = 1) {", " return erase(find(val), k);", " }", "", " // max (with xor-addition of val) and min (with xor-addition of val)", " Node* get_max(INT val = 0) {", " INT nval = val ^ lazy;", " Node* v = root;", " for (int i = MAX_DIGIT-1; i >= 0; --i) {", " bool flag = (nval >> i) & 1;", " if (!v->right) v = v->left;", " else if (!v->left) v = v->right;", " else if (flag) v = v->left;", " else v = v->right;", " }", " return v;", " }", " Node* get_min(INT val = 0) {", " return get_max(~val & ((INT(1)<left, *right = v->right;", " if ((lazy >> i) & 1) swap(left, right);", " if (left) return get_cur_node(left, i+1);", " else if (right) return get_cur_node(right, i+1);", " return v;", " }", " Node* get_next_node(Node *v, int i) {", " if (!v->prev) return nullptr;", " Node *left = v->prev->left, *right = v->prev->right;", " if ((lazy >> (i+1)) & 1) swap(left, right);", " if (v == left && right) return get_cur_node(right, i);", " else return get_next_node(v->prev, i+1);", " }", " Node* lower_bound(INT val) {", " INT nval = val ^ lazy;", " Node *v = root;", " for (int i = MAX_DIGIT-1; i >= 0; --i) {", " bool flag = (nval >> i) & 1;", " if (flag && v->right) v = v->right;", " else if (!flag && v->left) v = v->left;", " else if ((val >> i) & 1) return get_next_node(v, i);", " else return get_cur_node(v, i);", " }", " return v;", " }", " Node* upper_bound(INT val) {", " return lower_bound(val + 1);", " }", " size_t order_of_val(INT val) {", " Node *v = root;", " size_t res = 0;", " for (int i = MAX_DIGIT-1; i >= 0; --i) {", " Node *left = v->left, *right = v->right;", " if ((lazy >> i) & 1) swap(left, right);", " bool flag = (val >> i) & 1;", " if (flag) {", " res += get_count(left);", " v = right;", " }", " else v = left;", " }", " return res;", " }", "", " // k-th, k is 0-indexed", " Node* get_kth(size_t k, INT val = 0) {", " Node *v = root;", " if (get_count(v) <= k) return nullptr;", " for (int i = MAX_DIGIT-1; i >= 0; --i) {", " bool flag = (lazy >> i) & 1;", " Node *left = (flag ? v->right : v->left);", " Node *right = (flag ? v->left : v->right);", " if (get_count(left) <= k) k -= get_count(left), v = right;", " else v = left;", " }", " return v;", " }", "", " // debug", " void print(Node *v, string prefix = \"\") {", " if (!v) return;", " cout << prefix << \": \" << v->count << endl;", " print(v->left, prefix + \"0\");", " print(v->right, prefix + \"1\");", " }", " void print() {", " print(root);", " }", " vector eval(Node *v, int digit) const {", " vector res;", " if (!v) return res;", " if (!v->left && !v->right) {", " for (int i = 0; i < get_count(v); ++i) res.push_back(0);", " return res;", " }", " const auto& left = eval(v->left, digit-1);", " const auto& right = eval(v->right, digit-1);", " for (auto val : left) res.push_back(val);", " for (auto val : right) res.push_back(val + (INT(1)< eval() const {", " auto res = eval(root, MAX_DIGIT-1);", " for (auto &val : res) val ^= lazy;", " return res;", " }", " friend ostream& operator << (ostream &os, const BinaryTrie &bt) {", " auto res = bt.eval();", " for (auto val : res) os << val << \" \";", " return os;", " }", "};", "//https://drken1215.hatenablog.com/entry/2020/02/29/035900", "//BinaryTrie trie;", "//trie.root->count -> 集合のサイズ", "//trie.get_count(x) -> xの個数", "//trie.xor_query(val) -> 全体にvalをxor", "//trie.get(v) -> 遅延伝搬のため，取り出す時は基本的にこれを使う", "//trie.find(x) -> xがあるか", "//trie.insert(x,k=1) -> xをk個挿入", "//trie.erase(x) -> xを1個削除", "//trie.erase_k(x,k=1) -> xをk個削除", "//trie.get_max(val = 0) -> valとxorを取った時の最大値", "//trie.get_min(val = 0) -> valとxorを取った時の最小値", "//trie.get_kth(x) -> x番目(0-indexed)の値を取り出す．", "//trie.lower_bound(x) -> ", "//trie.upper_bound(x) -> ", "//trie.order_of_val(x) -> xが何番目か(0-indexed),xが集合にある場合のみ有効", "//trie.get_kth(x) -> 0indexedでx番目の値、x個無いならnullptr(<-int型、!get_kth(val)は可能)", "", ], "description": "BinaryTrie" }, "Segtree_2d": { "prefix": "atcoder_data_Segtree2d", "body": [ "template ", "struct SegmentTree2D {", " private:", " int id(int h, int w) { return h * 2 * W + w; }", " public:", " int H, W;", " vector seg;", " const F f;", " const T I;", " SegmentTree2D(int h, int w, F _f, const T& i) : f(_f), I(i) { init(h, w); }", "", " void init(int h, int w) {", " H = W = 1;", " while (H < h) H <<= 1;", " while (W < w) W <<= 1;", " seg.assign(4 * H * W, I);", " }", "", " // build にのみ呼ぶ", " void set(int h, int w, const T& x) { seg[id(h + H, w + W)] = x; }", "", " void build() {", " // w in [W, 2W)", " for (int w = W; w < 2 * W; w++) {", " for (int h = H - 1; h; h--) {", " seg[id(h, w)] = f(seg[id(2 * h + 0, w)], seg[id(2 * h + 1, w)]);", " }", " }", " // h in [0, 2H)", " for (int h = 0; h < 2 * H; h++) {", " for (int w = W - 1; w; w--) {", " seg[id(h, w)] = f(seg[id(h, 2 * w + 0)], seg[id(h, 2 * w + 1)]);", " }", " }", " }", "", " T get(int h, int w) { return seg[id(h + H, w + W)]; }", " // T operator()(int h, int w) const { return seg[id(h + H, w + W)]; }", "", " void update(int h, int w, const T& x) {", " h += H, w += W;", " seg[id(h, w)] = x;", " for (int i = h >> 1; i; i >>= 1) {", " seg[id(i, w)] = f(seg[id(2 * i + 0, w)], seg[id(2 * i + 1, w)]);", " }", " for (; h; h >>= 1) {", " for (int j = w >> 1; j; j >>= 1) {", " seg[id(h, j)] = f(seg[id(h, 2 * j + 0)], seg[id(h, 2 * j + 1)]);", " }", " }", " }", "", " T _inner_query(int h, int w1, int w2) {", " T res = I;", " for (; w1 < w2; w1 >>= 1, w2 >>= 1) {", " if (w1 & 1) res = f(res, seg[id(h, w1)]), w1++;", " if (w2 & 1) --w2, res = f(res, seg[id(h, w2)]);", " }", " return res;", " }", "", " // [ (h1,w1), (h2,w2) ) 半開", " T prod(int h1, int w1, int h2, int w2) {", " if (h1 >= h2 || w1 >= w2) return I;", " T res = I;", " h1 += H, h2 += H, w1 += W, w2 += W;", " for (; h1 < h2; h1 >>= 1, h2 >>= 1) {", " if (h1 & 1) res = f(res, _inner_query(h1, w1, w2)), h1++;", " if (h2 & 1) --h2, res = f(res, _inner_query(h2, w1, w2));", " }", " return res;", " }", "};", "", "/**", " * @brief 二次元セグメント木", " * @docs docs/data-structure-2d/2d-segment-tree.md", " * https://nyaannyaan.github.io/library/data-structure-2d/2d-segment-tree.hpp", " */", "// ", "// ll f(ll a, ll b){return a + b;}", "// ll e(){return 0ll;}", "// SegmentTree2D seg(H,W,f,e());", "" ], "description": "Segtree_2d" }, "bit2d": { "prefix": "atcoder_data_bit2d", "body": [ "template", "struct BIT2D{", " int H, W;", " vector> bit;", " BIT2D(int _H, int _W) : H(_H), W(_W){", " bit.resize(H, vector(W, 0));", " }", " // data[i][j] += v;", " void add(int i, int j, T v){", " for(int a = i + 1; a <= H; a += (a & -a)){", " for(int b = j + 1; b <= W; b += (b & - b)){", " bit[a - 1][b - 1] += v;", " }", " }", " }", " // [0, i) x [0, j)", " T _sum(int i, int j){", " T s = 0;", " for(int a = i; a > 0; a -= (a & -a)){", " for(int b = j; b > 0; b -= (b & -b)){", " s += bit[a - 1][b - 1];", " }", " }", " return s;", " }", " // [i1, i2) x [j1, j2)", " T sum(int i1, int j1, int i2, int j2){", " return _sum(i2, j2) - _sum(i2, j1) - _sum(i1, j2) + _sum(i1, j1);", " }", "};", "" ], "description": "bit2d" }, "Wavelet_Matrix": { "prefix": "atcoder_data_wavelet_matrix", "body": [ "// https://github.com/MitI-7/WaveletMatrix", "enum {", " NOTFOUND = 0xFFFFFFFFFFFFFFFFLLU // 18446744073709551615 ~ 1.8x10^20", "};", "", "class SuccinctBitVector {", "private:", " const uint64_t size; // ビットベクトルのサイズ", " static const uint64_t blockBitNum = 16;", " static const uint64_t LEVEL_L = 512;", " static const uint64_t LEVEL_S = 16;", "", " std::vector L; // 大ブロック", " std::vector S; // 小ブロック", " std::vector B; // ビットベクトル", "", " uint64_t numOne = 0; // 1bitの数", "", "public:", " explicit SuccinctBitVector(const uint64_t n) : size(n) {", " const uint64_t s = (n + blockBitNum - 1) / blockBitNum + 1; // ceil(n, blockSize)", " this->B.assign(s, 0);", " this->L.assign(n / LEVEL_L + 1, 0);", " this->S.assign(n / LEVEL_S + 1, 0);", " }", "", " // B[pos] = bit", " void setBit(const uint64_t bit, const uint64_t pos){", " assert(bit == 0 or bit == 1);", " assert(pos < this->size);", "", " const uint64_t blockPos = pos / blockBitNum;", " const uint64_t offset = pos % blockBitNum;", " if (bit == 1) { B.at(blockPos) |= (1LLU << offset); }", " else { B.at(blockPos) &= (~(1LLU << offset)); }", " }", "", " // B[pos]", " uint64_t access(const uint64_t pos) {", " assert(pos < this->size);", " const uint64_t blockPos = pos / blockBitNum;", " const uint64_t offset = pos % blockBitNum;", " return ((B.at(blockPos) >> offset) & 1);", " }", "", " void build() {", " uint64_t num = 0;", " for (uint64_t i = 0; i <= size; i++){", " if (i % LEVEL_L == 0) {", " L.at(i / LEVEL_L) = num;", " }", " if (i % LEVEL_S == 0) {", " S.at(i / LEVEL_S) = num - L.at(i / LEVEL_L);", " }", " if (i != size and i % blockBitNum == 0) {", " num += this->popCount(this->B.at(i / blockBitNum));", " }", " }", " this-> numOne = num;", " }", "", " // B[0, pos)のbitの数", " uint64_t rank(const uint64_t bit, const uint64_t pos) {", " assert(bit == 0 or bit == 1);", " assert(pos <= this->size);", "", " if (bit) {", " return L[pos / LEVEL_L] + S[pos / LEVEL_S] + popCount(B[pos / blockBitNum] & ((1 << (pos % blockBitNum)) - 1));", " }", " else {", " return pos - rank(1, pos);", " }", " }", "", " // rank番目のbitの位置 + 1(rankは1-origin)", " uint64_t select(const uint64_t bit, const uint64_t rank) {", " assert(bit == 0 or bit == 1);", " assert(rank > 0);", " if (bit == 0 and rank > this->size - this-> numOne) { return NOTFOUND; }", " if (bit == 1 and rank > this-> numOne) { return NOTFOUND; }", "", " // 大ブロックL内を検索", " uint64_t large_idx = 0;", " {", " uint64_t left = 0;", " uint64_t right = L.size();", " while (right - left > 1) {", " uint64_t mid = (left + right) / 2;", " uint64_t r = L.at(mid);", " r = (bit) ? r : mid * LEVEL_L - L.at(mid);", "", " if (r < rank) {", " left = mid;", " large_idx = mid;", " } else {", " right = mid;", " }", " }", " }", "", " // 小ブロックS内を検索", " uint64_t small_idx = (large_idx * LEVEL_L) / LEVEL_S;", " {", " uint64_t left = (large_idx * LEVEL_L) / LEVEL_S;", " uint64_t right = std::min(((large_idx + 1) * LEVEL_L) / LEVEL_S, (uint64_t)S.size());", " while (right - left > 1) {", " uint64_t mid = (left + right) / 2;", " uint64_t r = L.at(large_idx) + S.at(mid);", " r = (bit) ? r :mid * LEVEL_S - r;", "", " if (r < rank) {", " left = mid;", " small_idx = mid;", " } else {", " right = mid;", " }", " }", " }", "", " // Bをブロック単位で順番に探索", " uint64_t rank_pos = 0;", " {", " const uint64_t begin_block_idx = (small_idx * LEVEL_S) / blockBitNum;", " uint64_t total_bit = L.at(large_idx) + S.at(small_idx);", " if (bit == 0) {", " total_bit = small_idx * LEVEL_S - total_bit;", " }", " for (uint64_t i = 0;; ++i) {", " uint64_t b = popCount(B.at(begin_block_idx + i));", " if (bit == 0) {", " b = blockBitNum - b;", " }", " if (total_bit + b >= rank) {", " uint64_t block = (bit) ? B.at(begin_block_idx + i) : ~B.at(begin_block_idx + i);", " rank_pos = (begin_block_idx + i) * blockBitNum + selectInBlock(block, rank - total_bit);", " break;", " }", " total_bit += b;", " }", " }", "", " return rank_pos + 1;", " }", "", " uint64_t getNumOne() const {", " return numOne;", " }", "", " void debug() {", " std::cout << \"LEVEL_L(\" << L.size() << \")\" << std::endl;", " for (uint64_t i = 0 ; i < L.size(); ++i) {", " std::cout << L.at(i) << \", \";", " }", " std::cout << std::endl;", " std::cout << \"LEVEL_S(\" << S.size() << \")\" << std::endl;", " for (uint64_t i = 0 ; i < S.size(); ++i) {", " std::cout << S.at(i) << \", \";", " }", " std::cout << std::endl;", " }", "", "private:", " uint64_t popCount(uint64_t x) {", " x = (x & 0x5555555555555555ULL) + ((x >> 1) & 0x5555555555555555ULL);", " x = (x & 0x3333333333333333ULL) + ((x >> 2) & 0x3333333333333333ULL);", " x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0fULL;", " x = x + (x >> 8);", " x = x + (x >> 16);", " x = x + (x >> 32);", " return x & 0x7FLLU;", " }", "", " uint64_t selectInBlock(uint64_t x, uint64_t rank) {", " uint64_t x1 = x - ((x & 0xAAAAAAAAAAAAAAAALLU) >> 1);", " uint64_t x2 = (x1 & 0x3333333333333333LLU) + ((x1 >> 2) & 0x3333333333333333LLU);", " uint64_t x3 = (x2 + (x2 >> 4)) & 0x0F0F0F0F0F0F0F0FLLU;", "", " uint64_t pos = 0;", " for (;; pos += 8){", " uint64_t rank_next = (x3 >> pos) & 0xFFLLU;", " if (rank <= rank_next) break;", " rank -= rank_next;", " }", "", " uint64_t v2 = (x2 >> pos) & 0xFLLU;", " if (rank > v2) {", " rank -= v2;", " pos += 4;", " }", "", " uint64_t v1 = (x1 >> pos) & 0x3LLU;", " if (rank > v1){", " rank -= v1;", " pos += 2;", " }", "", " uint64_t v0 = (x >> pos) & 0x1LLU;", " if (v0 < rank){", " rank -= v0;", " pos += 1;", " }", "", " return pos;", " }", "};", "", "class WaveletMatrix {", "private:", " std::vector bit_arrays;", " std::vector begin_one; // 各bitに着目したときの1の開始位置", " std::map begin_alphabet; // 最後のソートされた配列で各文字の開始位置", " std::vector> cumulative_sum; // 各bitに着目したときの累積和", "", " uint64_t size; // 与えられた配列のサイズ", " uint64_t maximum_element; // 文字数", " uint64_t bit_size; // 文字を表すのに必要なbit数", "", "public:", " WaveletMatrix (const std::vector &array) {", " assert(array.size() > 0);", " size = array.size();", " maximum_element = *max_element(array.begin(), array.end()) + 1;", " bit_size = get_num_of_bit(maximum_element);", " if (bit_size == 0) {", " bit_size = 1;", " }", "", " for (uint64_t i = 0; i < bit_size; ++i) {", " SuccinctBitVector sv(size);", " bit_arrays.push_back(sv);", " }", " this->begin_one.resize(bit_size);", " this->cumulative_sum.resize(bit_size + 1, std::vector(size + 1, 0));", "", " for (uint64_t j = 0; j < array.size(); ++j) {", " this->cumulative_sum.at(0).at(j + 1) = this->cumulative_sum.at(0).at(j) + array[j];", " }", "", " std::vector v(array);", " for (uint64_t i = 0; i < bit_size; ++i) {", "", " std::vector temp;", " // 0をtempにいれてく", " for (uint64_t j = 0; j < v.size(); ++j) {", " uint64_t c = v.at(j);", " uint64_t bit = (c >> (bit_size - i - 1)) & 1; //　上からi番目のbit", " if (bit == 0) {", " temp.push_back(c);", " bit_arrays.at(i).setBit(0, j);", " }", " }", "", " this->begin_one.at(i) = temp.size();", "", " // 1をtempにいれてく", " for (uint64_t j = 0; j < v.size(); ++j) {", " uint64_t c = v.at(j);", " uint64_t bit = (c >> (bit_size - i - 1)) & 1; //　上からi番目のbit", " if (bit == 1) {", " temp.push_back(c);", " bit_arrays.at(i).setBit(1, j);", " }", " }", "", " for (uint64_t j = 0; j < temp.size(); ++j) {", " this->cumulative_sum.at(i + 1).at(j + 1) = this->cumulative_sum.at(i + 1).at(j) + temp.at(j);", " }", "", " bit_arrays.at(i).build();", " v = temp;", " }", "", " // ソートされた配列内での各文字の位置を取得", " for (int i = v.size() - 1; i >= 0; --i) {", " this->begin_alphabet[v.at(i)] = i;", " }", " }", "", " // v[pos]", " uint64_t access(uint64_t pos) {", " if (pos >= this->size) { return NOTFOUND; }", "", " uint64_t c = 0;", " for (uint64_t i = 0; i < bit_arrays.size(); ++i) {", " uint64_t bit = bit_arrays.at(i).access(pos); // もとの数値のi番目のbit", " c = (c <<= 1) | bit;", " pos = bit_arrays.at(i).rank(bit, pos);", " if (bit) {", " pos += this->begin_one.at(i);", " }", " }", " return c;", " }", "", " // i番目のcの位置 + 1を返す。rankは1-origin", " uint64_t select(uint64_t c, uint64_t rank) {", " assert(rank > 0);", " if (c >= maximum_element) {", " return NOTFOUND;", " }", " if (this->begin_alphabet.find(c) == this->begin_alphabet.end()) {", " return NOTFOUND;", " }", "", " uint64_t index = this->begin_alphabet.at(c) + rank;", " for (uint64_t i = 0; i < bit_arrays.size(); ++i){", " uint64_t bit = ((c >> i) & 1); // 下からi番目のbit", " if (bit == 1) {", " index -= this->begin_one.at(bit_size - i - 1);", " }", " index = this->bit_arrays.at(bit_size - i - 1).select(bit, index);", " }", " return index;", " }", "", " // v[begin_pos, end_pos)で最大値のindexを返す", " uint64_t maxRange(uint64_t begin_pos, uint64_t end_pos) {", " return quantileRange(begin_pos, end_pos, end_pos - begin_pos - 1);", " }", "", " // v[begin_pos, end_pos)で最小値のindexを返す", " uint64_t minRange(uint64_t begin_pos, uint64_t end_pos) {", " return quantileRange(begin_pos, end_pos, 0);", " }", "", " // v[begin_pos, end_pos)でk番目に小さい数値のindexを返す(kは0-origin)", " // つまり小さい順に並べてk番目の値", " uint64_t quantileRange(uint64_t begin_pos, uint64_t end_pos, uint64_t k) {", " if ((end_pos > size || begin_pos >= end_pos) || (k >= end_pos - begin_pos)) {", " return NOTFOUND;", " }", "", " uint64_t val = 0;", " for (uint64_t i = 0; i < bit_size; ++i) {", " const uint64_t num_of_zero_begin = bit_arrays.at(i).rank(0, begin_pos);", " const uint64_t num_of_zero_end = bit_arrays.at(i).rank(0, end_pos);", " const uint64_t num_of_zero = num_of_zero_end - num_of_zero_begin; // beginからendまでにある0の数", " const uint64_t bit = (k < num_of_zero) ? 0 : 1; // k番目の値の上からi番目のbitが0か1か", "", " if (bit) {", " k -= num_of_zero;", " begin_pos = this->begin_one.at(i) + begin_pos - num_of_zero_begin;", " end_pos = this->begin_one.at(i) + end_pos - num_of_zero_end;", " }", " else {", " begin_pos = num_of_zero_begin;", " end_pos = num_of_zero_begin + num_of_zero;", " }", "", " val = ((val << 1) | bit);", " }", "", " uint64_t left = 0;", " for (uint64_t i = 0; i < bit_size; ++i) {", " const uint64_t bit = (val >> (bit_size - i - 1)) & 1; // 上からi番目のbit", " left = bit_arrays.at(i).rank(bit, left); // cのi番目のbitと同じ数値の数", " if (bit) {", " left += this->begin_one.at(i);", " }", " }", "", " const uint64_t rank = begin_pos + k - left + 1;", " return select(val, rank) - 1;", " }", "", " // v[0, pos)のcの数", " uint64_t rank(uint64_t c, uint64_t pos) {", " assert(pos < size);", " if (c >= maximum_element) {", " return 0;", " }", " if (this->begin_alphabet.find(c) == this->begin_alphabet.end()) {", " return 0;", " }", "", " for (uint64_t i = 0; i < bit_size; ++i) {", " uint64_t bit = (c >> (bit_size - i - 1)) & 1; // 上からi番目のbit", " pos = bit_arrays.at(i).rank(bit, pos); // cのi番目のbitと同じ数値の数", " if (bit) {", " pos += this->begin_one.at(i);", " }", " }", "", " uint64_t begin_pos = this->begin_alphabet.at(c);", " return pos - begin_pos;", " }", "", " // v[begin_pos, end_pos)で[min, max)に入る値の個数", " uint64_t rangeFreq(uint64_t begin_pos, uint64_t end_pos, uint64_t min_c, uint64_t max_c) {", " if ((end_pos > size || begin_pos >= end_pos) || (min_c >= max_c) || min_c >= maximum_element) {", " return 0;", " }", "", " const auto maxi_t = rankAll(max_c, begin_pos, end_pos);", " const auto mini_t = rankAll(min_c, begin_pos, end_pos);", " return std::get<1>(maxi_t) - std::get<1>(mini_t);", " }", "", " // v[0, pos)でcより小さい文字の数 <- 恐らくv[begin, end)", " uint64_t rankLessThan(uint64_t c, uint64_t begin, uint64_t end) {", " auto t = rankAll(c, begin, end);", " return std::get<1>(t);", " }", "", " // v[0, pos)でcより大きい文字の数 <- 恐らくv[begin, end)", " uint64_t rankMoreThan(uint64_t c, uint64_t begin, uint64_t end) {", " auto t = rankAll(c, begin, end);", " return std::get<2>(t);", " }", "", " // v[begin, end)で(cと同じ値の数、cより小さい値の数、cより大きい値の数)を求める", " std::tuple rankAll(const uint64_t c, uint64_t begin, uint64_t end) {", " assert(end <= size);", " const uint64_t num = end - begin;", "", " if (begin >= end) {", " return std::make_tuple(0, 0, 0);", " }", " if (c >= maximum_element || end == 0) {", " return std::make_tuple(0, num, 0);", " }", "", " uint64_t rank_less_than = 0, rank_more_than = 0;", " for (size_t i = 0; i < bit_size && begin < end; ++i) {", " const uint64_t bit = (c >> (bit_size - i - 1)) & 1;", "", " const uint64_t rank0_begin = this->bit_arrays.at(i).rank(0, begin);", " const uint64_t rank0_end = this->bit_arrays.at(i).rank(0, end);", " const uint64_t rank1_begin = begin - rank0_begin;", " const uint64_t rank1_end = end - rank0_end;", "", " if (bit) {", " rank_less_than += (rank0_end - rank0_begin); // i番目のbitが0のものは除外される", " begin = this->begin_one.at(i) + rank1_begin;", " end = this->begin_one.at(i) + rank1_end;", " } else {", " rank_more_than += (rank1_end - rank1_begin); // i番目のbitが1のものは除外される", " begin = rank0_begin;", " end = rank0_end;", " }", " }", "", " const uint64_t rank = num - rank_less_than - rank_more_than;", " return std::make_tuple(rank, rank_less_than, rank_more_than);", " }", "", " // T[s, e)で出現回数が多い順にk個の(値，頻度)を返す", " // 頻度が同じ場合は値が小さいものが優先される", " std::vector> topk(uint64_t s, uint64_t e, uint64_t k) {", " assert(s < e);", " std::vector> result;", "", " // (頻度，深さ，値)の順でソート", " auto c = [](const std::tuple &l, const std::tuple &r) {", " // width", " if (std::get<0>(l) != std::get<0>(r)) {", " return std::get<0>(l) < std::get<0>(r);", " }", " // depth", " if (std::get<3>(l) != std::get<3>(r)) {", " return std::get<3>(l) > std::get<3>(r);", " }", " // value", " if (std::get<4>(l) != std::get<4>(r)) {", " return std::get<4>(l) > std::get<4>(r);", " }", " return true;", " };", "", " std::priority_queue, std::vector>, decltype(c)> que(c); // width, left, right, depth, value", " que.push(std::make_tuple(e - s, s, e, 0, 0));", "", " while (not que.empty()) {", " auto element = que.top(); que.pop();", " uint64_t width, left, right, depth, value;", " std::tie(width, left, right, depth, value) = element;", "", " if (depth >= this->bit_size) {", " result.emplace_back(std::make_pair(value, right - left));", " if (result.size() >= k) {", " break;", " }", " continue;", " }", "", " // 0", " const uint64_t left0 = this->bit_arrays.at(depth).rank(0, left);", " const uint64_t right0 = this->bit_arrays.at(depth).rank(0, right);", " if (left0 < right0) {", " que.push(std::make_tuple(right0 - left0, left0, right0, depth + 1, value));", " }", "", " // 1", " const uint64_t left1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, left);", " const uint64_t right1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, right);", " if (left1 < right1) {", " que.push(std::make_tuple(right1 - left1, left1, right1, depth + 1, value | (1 << (bit_size - depth - 1))));", " }", " }", "", " return result;", " };", "", " // T[begin_pos, end_pos)でx <= c < yを満たすcの和を返す", " uint64_t rangeSum(const uint64_t begin, const uint64_t end, const uint64_t x, const uint64_t y) {", " return rangeSum(begin, end, 0, 0, x, y);", " }", "", " // T[begin_pos, end_pos)でx <= c < yを満たす最大のcを返す", " uint64_t prevValue(const uint64_t begin_pos, const uint64_t end_pos, const uint64_t x, uint64_t y) {", " assert(end_pos <= size);", " const uint64_t num = end_pos - begin_pos;", "", " if (x >= y or y == 0) {", " return NOTFOUND;", " }", " if (y > maximum_element) {", " y = maximum_element;", " }", "", " if (begin_pos >= end_pos) {", " return NOTFOUND;", " }", " if (x >= maximum_element || end_pos == 0) {", " return NOTFOUND;", " }", "", " y--; // x <= c <= yにする", "", " std::stack> s; // (begin, end, depth, c, tight)", " s.emplace(std::make_tuple(begin_pos, end_pos, 0, 0, true));", "", " while (not s.empty()) {", " uint64_t b, e, depth, c;", " bool tight;", " std::tie(b, e, depth, c, tight) = s.top(); s.pop();", "", " if (depth == bit_size) {", " if (c >= x) {", " return c;", " }", " continue;", " }", "", " const uint64_t bit = (y >> (bit_size - depth - 1)) & 1;", "", " const uint64_t rank0_begin = this->bit_arrays.at(depth).rank(0, b);", " const uint64_t rank0_end = this->bit_arrays.at(depth).rank(0, e);", " const uint64_t rank1_begin = b - rank0_begin;", " const uint64_t rank1_end = e - rank0_end;", "", " // d番目のbitが0のものを使う", " const uint64_t b0 = rank0_begin;", " const uint64_t e0 = rank0_end;", " if (b0 != e0) { // 範囲がつぶれてない", " const uint64_t c0 = ((c << 1) | 0);", " s.emplace(std::make_tuple(b0, e0, depth + 1, c0, tight and bit == 0));", " }", "", " // d番目のbitが1のものを使う", " const uint64_t b1 = this->begin_one.at(depth) + rank1_begin;", " const uint64_t e1 = this->begin_one.at(depth) + rank1_end;", " if (b1 != e1) {", " if (not tight or bit == 1) {", " const auto c1 = ((c << 1) | 1);", " s.emplace(std::make_tuple(b1, e1, depth + 1, c1, tight));", " }", " }", " }", "", " return NOTFOUND;", " }", "", " // T[begin_pos, end_pos)でx <= c < yを満たす最小のcを返す", " uint64_t nextValue(const uint64_t begin_pos, const uint64_t end_pos, const uint64_t x, const uint64_t y) {", " assert(end_pos <= size);", " const uint64_t num = end_pos - begin_pos;", "", " if (x >= y or y == 0) {", " return NOTFOUND;", " }", "", " if (begin_pos >= end_pos) {", " return NOTFOUND;", " }", " if (x >= maximum_element || end_pos == 0) {", " return NOTFOUND;", " }", "", " std::stack> s; // (begin, end, depth, c, tight)", " s.emplace(std::make_tuple(begin_pos, end_pos, 0, 0, true));", "", " while (not s.empty()) {", " uint64_t b, e, depth, c;", " bool tight;", " std::tie(b, e, depth, c, tight) = s.top(); s.pop();", "", " if (depth == bit_size) {", " if (c < y) {", " return c;", " }", " continue;", " }", "", " const uint64_t bit = (x >> (bit_size - depth - 1)) & 1;", "", " const uint64_t rank0_begin = this->bit_arrays.at(depth).rank(0, b);", " const uint64_t rank0_end = this->bit_arrays.at(depth).rank(0, e);", " const uint64_t rank1_begin = b - rank0_begin;", " const uint64_t rank1_end = e - rank0_end;", "", " // d番目のbitが1のものを使う", " const uint64_t b1 = this->begin_one.at(depth) + rank1_begin;", " const uint64_t e1 = this->begin_one.at(depth) + rank1_end;", " if (b1 != e1) {", " const auto c1 = ((c << 1) | 1);", " s.emplace(std::make_tuple(b1, e1, depth + 1, c1, tight and bit == 1));", " }", "", " // d番目のbitが0のものを使う", " const uint64_t b0 = rank0_begin;", " const uint64_t e0 = rank0_end;", " if (b0 != e0) {", " if (not tight or bit == 0) {", " const uint64_t c0 = ((c << 1) | 0);", " s.emplace(std::make_tuple(b0, e0, depth + 1, c0, tight));", " }", " }", " }", "", " return NOTFOUND;", " }", "", " // T[s1, e1)とT[s2, e2)に共通して出現する要素を求める", " std::vector> intersect(uint64_t _s1, uint64_t _e1, uint64_t _s2, uint64_t _e2) {", " assert(_s1 < _e1);", " assert(_s2 < _e2);", "", " std::vector> intersection;", "", " std::queue> que; // s1, e1, s2, e2, depth, value", " que.push(std::make_tuple(_s1, _e1, _s2, _e2, 0, 0));", " while (not que.empty()) {", " auto e = que.front(); que.pop();", " uint64_t s1, e1, s2, e2, depth, value;", " std::tie(s1, e1, s2, e2, depth, value) = e;", "", " if (depth >= this->bit_size) {", " intersection.emplace_back(std::make_tuple(value, e1 - s1, e2 - s2));", " continue;", " }", "", " // 0", " uint64_t s1_0 = this->bit_arrays.at(depth).rank(0, s1);", " uint64_t e1_0 = this->bit_arrays.at(depth).rank(0, e1);", " uint64_t s2_0 = this->bit_arrays.at(depth).rank(0, s2);", " uint64_t e2_0 = this->bit_arrays.at(depth).rank(0, e2);", "", " if (s1_0 != e1_0 and s2_0 != e2_0) {", " que.push(std::make_tuple(s1_0, e1_0, s2_0, e2_0, depth + 1, value));", " }", "", " // 1", " uint64_t s1_1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, s1);", " uint64_t e1_1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, e1);", " uint64_t s2_1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, s2);", " uint64_t e2_1 = this->begin_one.at(depth) + this->bit_arrays.at(depth).rank(1, e2);", "", " if (s1_1 != e1_1 and s2_1 != e2_1) {", " que.push(std::make_tuple(s1_1, e1_1, s2_1, e2_1, depth + 1, value | (1 << bit_size - depth - 1)));", " }", " }", "", " return intersection;", " };", "", "private:", " uint64_t get_num_of_bit(uint64_t x) {", " if (x == 0) return 0;", " x--;", " uint64_t bit_num = 0;", " while (x >> bit_num) {", " ++bit_num;", " }", " return bit_num;", " }", "", " uint64_t rangeSum(const uint64_t begin, const uint64_t end, const uint64_t depth, const uint64_t c, const uint64_t x, const uint64_t y) {", " if (begin == end) {", " return 0;", " }", "", " if (depth == bit_size) {", " if (x <= c and c < y) {", " return c * (end - begin); // 値 * 頻度", " }", " return 0;", " }", "", " const uint64_t next_c = ((uint64_t)1 << (bit_size - depth - 1)) | c; // 上からdepth番目のbitを立てる", " const uint64_t all_one_c = (((uint64_t)1 << (bit_size - depth - 1)) - 1) | next_c; // depth以降のbitをたてる(これ以降全部1を選んだときの値)", " if(all_one_c < x or y <= c) {", " return 0;", " }", "", " // [begin, pos)のすべての要素は[x, y)", " if (x <= c and all_one_c < y) {", " return this->cumulative_sum.at(depth).at(end) - this->cumulative_sum.at(depth).at(begin);", " }", "", " const uint64_t rank0_begin = this->bit_arrays.at(depth).rank(0, begin);", " const uint64_t rank0_end = this->bit_arrays.at(depth).rank(0, end);", " const uint64_t rank1_begin = begin - rank0_begin;", " const uint64_t rank1_end = end - rank0_end;", "", " return rangeSum(rank0_begin, rank0_end, depth + 1, c, x, y) +", " rangeSum(this->begin_one.at(depth) + rank1_begin, this->begin_one[depth] + rank1_end, depth + 1, next_c, x, y);", " }", "};", "// vector vec(N);", "// WaveletMatrix wm(vec);", "// wm.access(i)", "// wm.select(val, rank)", "// wm.maxRange(left, right)", "// wm.minRange(left, right)", "// wm.quantileRange(left, right, k)", "// wm.rank(right)", "// wm.rangeFreq(left, right, min_val, max_val)", "// wm.rankLessThan(val, left, right)", "// wm.rankMoreThan(val, left, right)", "// wm.rankAll(val, left, right)", "// wm.topk(left, right, k)", "// wm.rangeSum(left, right, val_left, val_right)", "// wm.prevValue(left, right, val_left, val_right)", "// wm.nextValue(left, right, val_left, val_right)", "// wm.intersect(left1, right1, left2, right2)", "" ], "description": "Wavelet_Matrix" }, // //math // "itertools": { "prefix": "atcoder_math_itertools", "body": [ "/**", " * @brief nHrの配列を返す", " * ", " * @tparam T 要素の型", " * @param arr 長さnの配列", " * @param r 重複組合せで選ぶ数r", " * @return vector> nHrの結果を辞書順昇順で返す", " */", "template", "vector> combination_with_replacement(vector &arr, int r){", " vector> res;", " function&, int)> dfs = [&](vector &e, int idx){", " if ((int)e.size() == r) {", " res.push_back(e);", " return;", " }", " else {", " for(int i = idx; i < (int)arr.size(); i++){", " e.push_back(arr[i]);", " dfs(e, i);", " e.pop_back();", " }", " }", " };", " vector e = {};", " dfs(e, 0);", " return res;", "}", "", "/**", " * @brief nCrの配列を返す", " * ", " * @tparam T 要素の型", " * @param arr 長さnの配列", " * @param r 組み合わせで選ぶ数r", " * @return vector> nCrの結果を辞書順昇順で返す", " */", "template", "vector> combinations(vector &arr, int r){", " vector> res;", " int n = arr.size();", " function&, int)> dfs = [&](vector &e, int idx){", " if ((int)e.size() == r) {", " res.push_back(e);", " return;", " }", " if (idx == n) return;", "", " if (e.size() + (n - (idx + 1)) >= r) dfs(e, idx + 1);", "", " e.push_back(arr[idx]);", " if (e.size() + (n - (idx + 1)) >= r) dfs(e, idx + 1);", " e.pop_back();", " };", " vector e = {};", " dfs(e, 0);", " reverse(res.begin(), res.end());", " return res;", "}", "", "/**", " * @brief nPrの配列を返す", " * ", " * @tparam T 要素の型", " * @param arr 長さnの配列", " * @param r 組み合わせで選ぶ数r", " * @param dflag 昇順にソートするならtrue(デフォルトはfalse);", " * @return vector> nPrの結果を返す", " */", "template", "vector> permutations(vector &arr, int r, bool dflag=false){", " vector> res;", " auto combs = combinations(arr, r);", " for(auto ptn : combs){", " do{", " res.push_back(ptn);", " }while(next_permutation(all(ptn)));", " }", " if(dflag) {", " auto cmp = [](vector &lhs, vector &rhs){", " int nl = lhs.size();", " int nr = rhs.size();", " for(int i = 0; i < min(nl, nr); i++){", " if(lhs[i] == rhs[i]) continue;", " return (lhs[i] < rhs[i]);", " }", " return (nl < nr);", " };", " sort(all(res), cmp);", " }", " return res;", "}", "", "template", "vector> _productRecurse(vector &choices, int repeat, vector> &result){", " if (repeat == 0) return result;", "", " vector> nresult;", " for(vector re : result){", " for(T c : choices){", " vector temp = re;", " temp.push_back(c);", " nresult.push_back(temp);", " }", " }", "", " return _productRecurse(choices, repeat - 1, nresult);", "}", "", "/**", " * @brief 直積を返す ", " * ", " * @tparam T 要素の型", " * @param arr 長さnの配列", " * @param r 冪乗", " * @return vector> product({0, 1, 2}, 2) -> {{0, 0}, {0, 1}, {0, 2}, {1, 0}, {1, 1}, {1, 2}, {2, 0}, {2, 1}, {2, 2}}", " */", "template", "vector> product(vector &arr, int r=1){", " vector> emptyResult(1, vector{});", " return _productRecurse(arr, r, emptyResult);", "}", "" ], "description": "itertools" }, "python_like": { "prefix": "atcoder_math_python_like", "body": [ "// a // b in Python", "template", "T floor(T a, T b){", " if (a >= 0) return a / b;", " else {", " if (abs(a) % b == 0){", " return a/b;", " }", " else{", " return a/b-1;", " }", " }", "}", "", "// a % b in Python", "template", "T div_mod(T a, T b){", " if (a >= 0) return a % b;", " else{", " if (abs(a) % b == 0){", " return 0;", " }", " else{", " return b - abs(a) % b;", " }", " }", "}", "" ], "description": "python_like" }, "fps": { "prefix": "atcoder_math_fps", "body": [ "//形式的冪級数", "//https://qiita.com/gg_hatano/items/3591ddf267092c235a23", "#define rep2(i, m, n) for (int i = (m); i < (n); ++i)", "#define drep2(i, m, n) for (int i = (m)-1; i >= (n); --i)", "#define drep(i, n) drep2(i, n, 0)", "template", "struct FormalPowerSeries : vector {", " using vector::vector;", " using vector::operator=;", " using F = FormalPowerSeries;", " ", " F operator-() const {", " F res(*this);", " for (auto &e : res) e = -e;", " return res;", " }", " F &operator*=(const T &g) {", " for (auto &e : *this) e *= g;", " return *this;", " }", " F &operator/=(const T &g) {", " assert(g != T(0));", " *this *= g.inv();", " return *this;", " }", " F &operator+=(const F &g) {", " int n = (*this).size(), m = g.size();", " rep(i, min(n, m)) (*this)[i] += g[i];", " return *this;", " }", " F &operator-=(const F &g) {", " int n = (*this).size(), m = g.size();", " rep(i, min(n, m)) (*this)[i] -= g[i];", " return *this;", " }", " F &operator<<=(const int d) {", " int n = (*this).size();", " (*this).insert((*this).begin(), d, 0);", " (*this).resize(n);", " return *this;", " }", " F &operator>>=(const int d) {", " int n = (*this).size();", " (*this).erase((*this).begin(), (*this).begin() + min(n, d));", " (*this).resize(n);", " return *this;", " }", " F inv(int d = -1) const {", " int n = (*this).size();", " assert(n != 0 && (*this)[0] != 0);", " if (d == -1) d = n;", " assert(d > 0);", " F res{(*this)[0].inv()};", " while (res.size() < d) {", " int m = size(res);", " F f(begin(*this), begin(*this) + min(n, 2*m));", " F r(res);", " f.resize(2*m), internal::butterfly(f);", " r.resize(2*m), internal::butterfly(r);", " rep(i, 2*m) f[i] *= r[i];", " internal::butterfly_inv(f);", " f.erase(f.begin(), f.begin() + m);", " f.resize(2*m), internal::butterfly(f);", " rep(i, 2*m) f[i] *= r[i];", " internal::butterfly_inv(f);", " T iz = T(2*m).inv(); iz *= -iz;", " rep(i, m) f[i] *= iz;", " res.insert(res.end(), f.begin(), f.begin() + m);", " }", " return {res.begin(), res.begin() + d};", " }", " ", " // fast: FMT-friendly modulus only", " F &operator*=(const F &g) {", " int n = (*this).size();", " *this = convolution(*this, g);", " (*this).resize(n);", " return *this;", " }", " F &operator/=(const F &g) {", " int n = (*this).size();", " *this = convolution(*this, g.inv(n));", " (*this).resize(n);", " return *this;", " }", " ", " // // naive", " // F &operator*=(const F &g) {", " // int n = (*this).size(), m = g.size();", " // drep(i, n) {", " // (*this)[i] *= g[0];", " // rep2(j, 1, min(i+1, m)) (*this)[i] += (*this)[i-j] * g[j];", " // }", " // return *this;", " // }", " // F &operator/=(const F &g) {", " // assert(g[0] != T(0));", " // T ig0 = g[0].inv();", " // int n = (*this).size(), m = g.size();", " // rep(i, n) {", " // rep2(j, 1, min(i+1, m)) (*this)[i] -= (*this)[i-j] * g[j];", " // (*this)[i] *= ig0;", " // }", " // return *this;", " // }", " ", " // sparse", " F &operator*=(vector> g) {", " int n = (*this).size();", " auto [d, c] = g.front();", " if (d == 0) g.erase(g.begin());", " else c = 0;", " drep(i, n) {", " (*this)[i] *= c;", " for (auto &[j, b] : g) {", " if (j > i) break;", " (*this)[i] += (*this)[i-j] * b;", " }", " }", " return *this;", " }", " F &operator/=(vector> g) {", " int n = (*this).size();", " auto [d, c] = g.front();", " assert(d == 0 && c != T(0));", " T ic = c.inv();", " g.erase(g.begin());", " rep(i, n) {", " for (auto &[j, b] : g) {", " if (j > i) break;", " (*this)[i] -= (*this)[i-j] * b;", " }", " (*this)[i] *= ic;", " }", " return *this;", " }", " ", " // multiply and divide (1 + cz^d)", " void multiply(const int d, const T c) { ", " int n = (*this).size();", " if (c == T(1)) drep(i, n-d) (*this)[i+d] += (*this)[i];", " else if (c == T(-1)) drep(i, n-d) (*this)[i+d] -= (*this)[i];", " else drep(i, n-d) (*this)[i+d] += (*this)[i] * c;", " }", " void divide(const int d, const T c) {", " int n = (*this).size();", " if (c == T(1)) rep(i, n-d) (*this)[i+d] -= (*this)[i];", " else if (c == T(-1)) rep(i, n-d) (*this)[i+d] += (*this)[i];", " else rep(i, n-d) (*this)[i+d] -= (*this)[i] * c;", " }", " ", " T eval(const T &a) const {", " T x(1), res(0);", " for (auto e : *this) res += e * x, x *= a;", " return res;", " }", " ", " F operator*(const T &g) const { return F(*this) *= g; }", " F operator/(const T &g) const { return F(*this) /= g; }", " F operator+(const F &g) const { return F(*this) += g; }", " F operator-(const F &g) const { return F(*this) -= g; }", " F operator<<(const int d) const { return F(*this) <<= d; }", " F operator>>(const int d) const { return F(*this) >>= d; }", " F operator*(const F &g) const { return F(*this) *= g; }", " F operator/(const F &g) const { return F(*this) /= g; }", " F operator*(vector> g) const { return F(*this) *= g; }", " F operator/(vector> g) const { return F(*this) /= g; }", "};", "using mint = modint998244353;", "using fps = FormalPowerSeries;", "using sfps = vector>; // (次数，係数)", " " ], "description": "fps" }, "arbitrary": { "prefix": "atcoder_math_cmb_arbitrary", "body": [ "struct Barrett {", " using u32 = unsigned int;", " using i64 = long long;", " using u64 = unsigned long long;", " u32 m;", " u64 im;", " Barrett() : m(), im() {}", " Barrett(int n) : m(n), im(u64(-1) / m + 1) {}", " constexpr inline i64 quo(u64 n) {", " u64 x = u64((__uint128_t(n) * im) >> 64);", " u32 r = n - x * m;", " return m <= r ? x - 1 : x;", " }", " constexpr inline i64 rem(u64 n) {", " u64 x = u64((__uint128_t(n) * im) >> 64);", " u32 r = n - x * m;", " return m <= r ? r + m : r;", " }", " constexpr inline pair quorem(u64 n) {", " u64 x = u64((__uint128_t(n) * im) >> 64);", " u32 r = n - x * m;", " if (m <= r) return {x - 1, r + m};", " return {x, r};", " }", " constexpr inline i64 pow(u64 n, i64 p) {", " u32 a = rem(n), r = m == 1 ? 0 : 1;", " while (p) {", " if (p & 1) r = rem(u64(r) * a);", " a = rem(u64(a) * a);", " p >>= 1;", " }", " return r;", " }", "};", "", "#define PRIME_POWER_BINOMIAL_M_MAX ((1LL << 30) - 1)", "#define PRIME_POWER_BINOMIAL_N_MAX 20000000", "", "struct prime_power_binomial {", " int p, q, M;", " vector fac, ifac, inv;", " int delta;", " Barrett bm, bp;", "", " prime_power_binomial(int _p, int _q) : p(_p), q(_q) {", " assert(1 < p && p <= PRIME_POWER_BINOMIAL_M_MAX);", " assert(_q > 0);", " long long m = 1;", " while (_q--) {", " m *= p;", " assert(m <= PRIME_POWER_BINOMIAL_M_MAX);", " }", " M = m;", " bm = Barrett(M), bp = Barrett(p);", " enumerate();", " delta = (p == 2 && q >= 3) ? 1 : M - 1;", " }", "", " void enumerate() {", " int MX = min(M, PRIME_POWER_BINOMIAL_N_MAX + 10);", " fac.resize(MX);", " ifac.resize(MX);", " inv.resize(MX);", " fac[0] = ifac[0] = inv[0] = 1;", " fac[1] = ifac[1] = inv[1] = 1;", " for (int i = 2; i < MX; i++) {", " if (i % p == 0) {", " fac[i] = fac[i - 1];", " fac[i + 1] = bm.rem(1LL * fac[i - 1] * (i + 1));", " i++;", " } else {", " fac[i] = bm.rem(1LL * fac[i - 1] * i);", " }", " }", " ifac[MX - 1] = bm.pow(fac[MX - 1], M / p * (p - 1) - 1);", " for (int i = MX - 2; i > 1; --i) {", " if (i % p == 0) {", " ifac[i] = bm.rem(1LL * ifac[i + 1] * (i + 1));", " ifac[i - 1] = ifac[i];", " i--;", " } else {", " ifac[i] = bm.rem(1LL * ifac[i + 1] * (i + 1));", " }", " }", " }", "", " long long Lucas(long long n, long long m) {", " int res = 1;", " while (n) {", " int n0, m0;", " tie(n, n0) = bp.quorem(n);", " tie(m, m0) = bp.quorem(m);", " if (n0 < m0) return 0;", " res = bm.rem(1LL * res * fac[n0]);", " int buf = bm.rem(1LL * ifac[n0 - m0] * ifac[m0]);", " res = bm.rem(1LL * res * buf);", " }", " return res;", " }", "", " long long C(long long n, long long m) {", " if (n < m || n < 0 || m < 0) return 0;", " if (q == 1) return Lucas(n, m);", " long long r = n - m;", " int e0 = 0, eq = 0, i = 0;", " int res = 1;", " while (n) {", " res = bm.rem(1LL * res * fac[bm.rem(n)]);", " res = bm.rem(1LL * res * ifac[bm.rem(m)]);", " res = bm.rem(1LL * res * ifac[bm.rem(r)]);", " n = bp.quo(n);", " m = bp.quo(m);", " r = bp.quo(r);", " int eps = n - m - r;", " e0 += eps;", " if (e0 >= q) return 0;", " if (++i >= q) eq += eps;", " }", " if (eq & 1) res = bm.rem(1LL * res * delta);", " res = bm.rem(1LL * res * bm.pow(p, e0));", " return res;", " }", "};", "", "// constraints:", "// (M <= 1e7 and max(N) <= 1e18) or (M < 2^30 and max(N) <= 2e7)", "struct arbitrary_mod_binomial {", " int mod;", " vector M;", " vector cs;", "", " arbitrary_mod_binomial(long long md) : mod(md) {", " assert(1 <= md);", " assert(md <= PRIME_POWER_BINOMIAL_M_MAX);", " for (int i = 2; i * i <= md; i++) {", " if (md % i == 0) {", " int j = 0, k = 1;", " while (md % i == 0) md /= i, j++, k *= i;", " M.push_back(k);", " cs.emplace_back(i, j);", " assert(M.back() == cs.back().M);", " }", " }", " if (md != 1) {", " M.push_back(md);", " cs.emplace_back(md, 1);", " }", " assert(M.size() == cs.size());", " }", "", " long long C(long long n, long long m) {", " if (mod == 1) return 0;", " vector rem, d;", " for (int i = 0; i < (int)cs.size(); i++) {", " rem.push_back(cs[i].C(n, m));", " d.push_back(M[i]);", " }", " return atcoder::crt(rem, d).first;", " }", "};", "", "#undef PRIME_POWER_BINOMIAL_M_MAX", "#undef PRIME_POWER_BINOMIAL_N_MAX", "", "/**", " * @brief 任意mod二項係数", " * @docs docs/modulo/arbitrary-mod-binomial.md", " */", "// arbitrary_mod_binomial coef(MOD);", "// coef.C(N,K);", "" ], "description": "arbitrary" }, "combination": { "prefix": "atcoder_math_cmb", "body": [ "//https://drken1215.hatenablog.com/entry/2018/06/08/210000", "//COMinit()を忘れない!!!", "const ll NMAX = 202020;", "const ll MOD = 998244353;", "//const int MOD = 1e9+7;", "", "ll fac[NMAX],finv[NMAX],inv[NMAX];", "", "void COMinit(){", " fac[0] = fac[1] = 1LL;", " finv[0] = finv[1] = 1LL;", " inv[1] = 1LL;", " for (int i=2;i(B[0].size()));", " for (int i = 0; i < A.size(); ++i) {", " for (int k = 0; k < B.size(); k++) {", " for (int j = 0; j < B[0].size(); j++) {", " C[i][j] = (C[i][j] + (A[i][k] * B[k][j]) % M) % M;", " }", " }", " }", " return C;", "}", "", "mat mat_pow(mat &A, ll k) {", " mat res(A.size(), vector(A.size()));", " for (int i = 0; i < res.size(); i++) {", " res[i][i] = 1;", " }", " while (k > 0) {", " if (k & 1) res = mat_mul(res, A);", " A = mat_mul(A, A);", " k >>= 1;", " }", " return res;", "}" ], "description": "matrix_skeir" }, "matrix": { "prefix": "atcoder_math_matrix", "body": [ "// https://youtu.be/ylWYSurx10A?t=2352", "template", "struct Matrix{", " int h, w;", " vector> d;", " Matrix(): h(0), w(0) {}", " Matrix(int h, int w, T val=0): h(h), w(w), d(h, vector(w,val)) {}", " Matrix(int n, T val=0): h(n), w(n), d(n, vector(n,val)) {}", "", " Matrix& unit(){", " assert(h == w);", " rep(i,h) d[i][i] = 1;", " return *this;", " }", "", " const vector& operator[](int i) const { return d[i];}", " vector& operator[](int i) { return d[i];}", "", " Matrix operator+(const Matrix& a) const {", " assert(h == a.h && w == a.w);", " Matrix r(h, w);", " rep(i,h)rep(j,w){", " r[i][j] = d[i][j] + a[i][j];", " }", " return r;", " }", "", " Matrix &operator+=(const Matrix& a) const {", " assert(h == a.h && w == a.w);", " rep(i,h)rep(j,w){", " (*this)[i][j] += a[i][j];", " }", " return (*this);", " }", "", " Matrix operator-(const Matrix& a) const {", " assert(h == a.h && w == a.w);", " Matrix r(h, w);", " rep(i,h)rep(j,w){", " r[i][j] = d[i][j] - a[i][j];", " }", " return r;", " }", "", " Matrix &operator-=(const Matrix& a) const {", " assert(h == a.h && w == a.w);", " rep(i,h)rep(j,w){", " (*this)[i][j] -= a[i][j];", " }", " return (*this);", " }", "", " Matrix operator*(const Matrix& a) const {", " assert(w == a.h);", " Matrix r(h, a.w);", " rep(i,h)rep(k,w)rep(j,a.w){", " r[i][j] += d[i][k] * a[k][j];", " }", " return r;", " }", "", " Matrix &operator*=(const Matrix& a) const {", " assert(w == a.h);", " vector> nd(h, vector(w));", " rep(i,h)rep(k,w)rep(j,a.w){", " nd[i][j] += (*this)[i][k] * a[k][j];", " }", " d = move(nd);", " return (*this);", " }", "", " vector operator*(const vector &a) const {", " // res[i] = sum{ M[i][j] * x[j] } (j = 0 ... h-1)", " assert(w == (int)a.size());", " vector r(h);", " rep(i,h)rep(j,w){", " r[i] += (*this)[i][j] * a[j];", " }", " return r;", " }", "", " Matrix operator*(const T &a) const {", " Matrix r(h, w);", " rep(i,h)rep(j,w){", " r[i][j] = (*this)[i][j] * a;", " }", " return r;", " }", "", " Matrix &operator*=(const T &a) const {", " vector> nd(h, vector(w));", " rep(i,h)rep(j,w){", " nd[i][j] = (*this)[i][j] * a;", " }", " d = move(nd);", " return (*this);", " }", "", " bool operator==(const Matrix &a){", " if(h != a.h || w != a.w) return false;", " rep(i,h)rep(j,w){", " if((*this)[i][j] != a[i][j]) return false;", " }", " return true;", " }", "", " friend ostream &operator<<(ostream &os, Matrix &a){", " rep(i,a.h){", " os << (i == 0 ? '[' : ' ');", " rep(j,a.w) os << (j == 0 ? '[' : ' ') << a[i][j] << (j == a.w - 1 ? \"]\" : \",\");", " os << (i == a.h - 1 ? \"]\" : \",\") << '\\n';", " }", " return os;", " }", "", "", " pair shape() {return {this->h, this->w};}", "", " static Matrix eye(int n){", " Matrix mat(n, n);", " mat.unit();", " return mat;", " }", "", " Matrix pow(long long t) const {", " assert(h == w);", " if(!t) Matrix(h, h).unit();", " if(t == 1) return *this;", " Matrix r = pow(t >> 1);", " r = r * r;", " if(t & 1) r = r * (*this);", " return r;", " }", "", " T det(){", " assert(h == w);", " vector> dc = d;", " T res = 1;", " rep(k,h){", " for(int i = k; i < h; i++){", " if(dc[i][k] == 0) continue;", " if(i != k){", " swap(dc[i], dc[k]);", " res = -res;", " }", " }", " if(dc[k][k] == 0) return 0;", " res *= dc[k][k];", " T inv = T(1) / dc[k][k];", " rep(j,h) dc[k][j] *= inv;", " for(int i = k + 1; i < h; i++){", " T c = dc[i][k];", " for(int j = k; j < h; j++) dc[i][j] -= dc[k][j] * c;", " }", " }", " return res;", " }", "", " Matrix inv(){", " assert(h == w);", " int n = h;", " // (A E) -> (E, invA)", " Matrix AE(n, 2 * n);", " rep(i,n){", " rep(j,n) AE[i][j] = d[i][j];", " AE[i][i + n] = 1;", " }", "", " rep(r, n){", " int pivot = -1;", " for(int i = r; i < n; i++){", " if(AE[i][r] != 0){", " pivot = i;", " break;", " }", " }", " // 逆行列が存在しない", " if(pivot == -1) return Matrix();", " swap(AE[r], AE[pivot]);", "", " for(int j = r + 1; j < 2 * n; j++) AE[r][j] /= AE[r][r];", " rep(i,n)if(i != r){", " for(int j = r + 1; j < 2 * n; j++){", " AE[i][j] -= AE[i][r] * AE[r][j];", " }", " }", " }", "", " Matrix r(n, n);", " rep(i,n)rep(j,n) r[i][j] = AE[i][j + n];", " return r;", " }", "", " // !! not verify !!", " vector linear_equation(vector b){", " Matrix invA = (*this).inv();", " if(invA.h == 0) return {};", " return invA * b;", " }", "};", "", "// Matrix mat(h, w);", "// Matrix identity = Matrix::eye(n);", "// pii hw = mat.shape();", "// T determinant = A.det();", "// Matrix powA = A.pow(K);", "// Matrix invA = A.pow(K);", "// vector x = A.linear_equation(b);", "" ], "description": "matrix" }, "Millar_Rabin": { "prefix": "atcoder_math_Miller_Rabin", "body": [ "// A ^ N を M で割ったあまり", "template T pow_mod(T A, T N, T M) {", " T res = 1 % M;", " A %= M;", " while (N) {", " if (N & 1) res = (res * A) % M;", " A = (A * A) % M;", " N >>= 1;", " }", " return res;", "}", "", "// Miller-Rabin 素数判定", "bool Miller_Rabin(long long N) {", " if (N <= 1) return false;", " if (N == 2) return true;", " if (N % 2 == 0) return false;", " vector A = {2, 325, 9375, 28178, 450775,", " 9780504, 1795265022};", " long long s = 0, d = N - 1;", " while (d % 2 == 0) {", " ++s;", " d >>= 1;", " }", " for (auto a : A) {", " if (a % N == 0) return true;", " long long t, x = pow_mod<__int128_t>(a, d, N);", " if (x != 1) {", " for (t = 0; t < s; ++t) {", " if (x == N - 1) break;", " x = __int128_t(x) * x % N;", " }", " if (t == s) return false;", " }", " }", " return true;", "}", "" ], "description": "Millar_Rabin" }, "math": { "prefix": "atcoder_math_Pollard", "body": [ "// https://algo-method.com/tasks/553/editorial", "// Miller-Rabin 素数判定法", "template T pow_mod(T A, T N, T M) {", " T res = 1 % M;", " A %= M;", " while (N) {", " if (N & 1) res = (res * A) % M;", " A = (A * A) % M;", " N >>= 1;", " }", " return res;", "}", "", "bool is_prime(long long N) {", " if (N <= 1) return false;", " if (N == 2 || N == 3) return true;", " if (N % 2 == 0) return false;", " vector A = {2, 325, 9375, 28178, 450775,", " 9780504, 1795265022};", " long long s = 0, d = N - 1;", " while (d % 2 == 0) {", " ++s;", " d >>= 1;", " }", " for (auto a : A) {", " if (a % N == 0) return true;", " long long t, x = pow_mod<__int128_t>(a, d, N);", " if (x != 1) {", " for (t = 0; t < s; ++t) {", " if (x == N - 1) break;", " x = __int128_t(x) * x % N;", " }", " if (t == s) return false;", " }", " }", " return true;", "}", "", "// Pollard のロー法", "long long gcd(long long A, long long B) {", " A = abs(A), B = abs(B);", " if (B == 0) return A;", " else return gcd(B, A % B);", "}", " ", "long long pollard(long long N) {", " if (N % 2 == 0) return 2;", " if (is_prime(N)) return N;", "", " auto f = [&](long long x) -> long long {", " return (__int128_t(x) * x + 1) % N;", " };", " long long step = 0;", " while (true) {", " ++step;", " long long x = step, y = f(x);", " while (true) {", " long long p = gcd(y - x + N, N);", " if (p == 0 || p == N) break;", " if (p != 1) return p;", " x = f(x);", " y = f(f(y));", " }", " }", "}", "", "vector prime_factorize(long long N) {", " if (N == 1) return {};", " long long p = pollard(N);", " if (p == N) return {p};", " vector left = prime_factorize(p);", " vector right = prime_factorize(N / p);", " left.insert(left.end(), right.begin(), right.end());", " sort(left.begin(), left.end());", " return left;", "}", "" ], "description": "math" }, "is_prime": { "prefix": "atcoder_math_isprime", "body": [ "//O(sqrt(N))", "bool is_prime(ll n){", " for(ll i=2;i*i<=n;i++){", " if (n % i == 0) return false;", " }", " return true;", "}", "" ], "description": "is_prime" }, "euler_phi": { "prefix": "atcoder_math_euler_phi", "body": [ "", "ll euler_phi(ll n){", " ll res = n;", " for(ll i = 2; i * i <= n; i++){", " if (n % i) continue;", " res = res - res / i;", " while((n % i) == 0) n /= i;", " }", " if (n != 1) res = res - res / n;", " return res;", "}", "" ], "description": "euler_phi" }, "Eratosthenes": { "prefix": "atcoder_math_Eratosthenes", "body": [ "// https://qiita.com/drken/items/3beb679e54266f20ab63", "struct Eratosthenes{", " int N;", " vector isprime;", " vector minfactor, mobius;", " Eratosthenes(int N_max = 1e7){init(N_max);}", " //初期化", " void init(int N_max = 1e7){", " int N = N_max;", " isprime.assign(N+1,true);", " minfactor.assign(N+1,-1);", " mobius.assign(N+1,1);", " //Eratosthenes O(NloglogN)", " isprime[0] = false;", " isprime[1] = false;", " for(int p=2;p<=N;p++){", " if (!isprime[p])continue;", " minfactor[p] = p;", " mobius[p] = -1;", " //pの倍数の処理", " for(int q=2*p;q<=N;q+=p){", " isprime[q] = false;", " if (minfactor[q] == -1){", " minfactor[q] = p;", " }", " if ((q/p) % p == 0) mobius[q] = 0;", " else mobius[q] *= -1;", " }", " }", " }", " //素数判定,O(1)", " bool judge_prime(int num){", " return isprime[num];", " }", " //素数列挙,O(N)", " vector list_primes(int num = -1){", " if (num == -1) num = N;", " vector primes;", " for(int p=0;p<=num;p++){", " if (isprime[p]) primes.push_back(p);", " }", " return primes;", " }", " //高速素因数分解,O(logN),{(素因数,個数)...}", " vector factorize(int x){", " vector ans;", " while(x > 1){", " int p = minfactor[x];", " int e = 0;", " while(minfactor[x] == p){", " x /= p;", " e++;", " }", " ans.push_back(make_pair(p,e));", " }", " return ans;", " }", " //高速約数列挙 O(240(N <= 1e6),1344(N <= 1e9))", " vector divisors(int x){", " vector ans; ans.push_back(1);", " vector facts = factorize(x);", " for(auto [p,e]:facts){", " int s = ans.size();", " for(int i=0;i mobius[n] = 0", " //mobius[n] = pow(-1,Nの素数の種類)", " int my_mobius(int x){", " return mobius[x];", " }", "};", "", "// f -> F, 累積和Fを求める", "template", "vector fast_zeta(vector &f){", " vector res = f;", " int N = f.size() - 1; ", " Eratosthenes er(N);", " for(int p=2;p<=N;p++){", " if (!er.judge_prime(p)) continue;", " for(int k=(N/p);k>0;k--){", " res[k] += res[k * p];", " }", " }", " return res;", "}", "", "// F -> f, 累積和Fを分解する", "template", "vector fast_mobius(vector &F){", " vector res = F;", " int N = F.size() - 1; ", " Eratosthenes er(N);", " for(int p=2;p<=N;p++){", " if (!er.judge_prime(p)) continue;", " for(int k=1;k<=(N/p);k++){", " res[k] -= res[k * p];", " }", " }", " return res;", "}", "", "template", "vector gcd_conv(vector &f, vector &g){", " int N = max(f.size(), g.size());", " vector F(N+1) , G(N+1), H(N+1);", " for(int i=0;i prime_factorize(ll n){", " vector res;", " for(ll i = 2; i * i <= n ; i++){", " if(n % i != 0ll)continue;", " ll tmp = 0ll;", " while(n % i == 0ll){", " tmp++;", " n /= i;", " }", " res.push_back(make_pair(i,tmp));", " }", " if (n != 1ll) res.push_back(make_pair(n,1ll));", " return res;", "}", "" ], "description": "factorize" }, "make_divisors": { "prefix": "atcoder_math_divisors", "body": [ "vector make_divisors(ll n){", " vector divisors;", " ll i = 1;", " while (i * i <= n){", " if (n % i == 0){", " divisors.push_back(i);", " if (i != (n/i)) divisors.push_back(n/i);", " }", " i++;", " }", " sort(all(divisors));", " return divisors;", "}", "" ], "description": "make_divisors" }, "modpow": { "prefix": "atcoder_math_modpow", "body": [ "long long modpow(long long x, long long n, long long MOD) {", " long long ret = 1;", " while (n > 0) {", " if (n & 1) ret = ret * x % MOD; // n の最下位bitが 1 ならば x^(2^i) をかける", " x = x * x % MOD;", " n >>= 1; // n を1bit 左にずらす", " }", " return ret;", "}", "" ], "description": "modpow" }, // // graph theory // "dijkstra": { "prefix": "atcoder_graph_dijkstra", "body": [ "using Edge = pair;", "using Graph = vector>;", "vector dijkstra(int st, Graph &g){", " int N = g.size();", " vector dist(N, LINF);", " dist[st] = 0ll;", " using P = pair;", " priority_queue, greater

> pq;", " pq.emplace(P{0ll, st});", " while(!pq.empty()){", " ll time = pq.top().first;", " int now = pq.top().second;", " pq.pop();", " if (time > dist[now])continue;", " for(auto e : g[now]){", " ll c = e.first;", " int nxt = e.second;", " if (c + time < dist[nxt]){", " dist[nxt] = c + time;", " pq.push(P{c + time, nxt});", " }", " }", " }", " return dist;", "}", "" ], "description": "dijkstra" }, "bfs": { "prefix": "atcoder_graph_bfs", "body": [ "vector bfs(int st, Graph &g){", " int N = g.size();", " queue que;", " que.push(st);", " vector dist(N,LINF);", " dist[st] = 0;", " while(!que.empty()){", " auto now = que.front();que.pop();", " for(auto nxt : g[now]){", " if (dist[nxt] != LINF)continue;", " dist[nxt] = dist[now] + 1;", " que.push(nxt);", " }", " }", " return dist;", "}", "" ], "description": "bfs" }, "bellman_ford": { "prefix": "atcoder_graph_bellman_ford", "body": [ "// https://yukicoder.me/submissions/968942", "using Edge = tuple; // (weight, now, nxt)", "pair, vector> bellman_ford(int V, int st, vector &edges){", " vector dist(V, LINF), negative(V, false); // negative[i] ... iが負閉路に含まれるならtrue", " dist[st] = 0;", " for(int i = 0; i < V - 1; i++){", " bool update = false;", " for(auto &e : edges){", " ll weight;", " int now, nxt;", " tie(weight, now, nxt) = e;", " if(dist[now] != LINF && dist[nxt] > dist[now] + weight){", " dist[nxt] = dist[now] + weight;", " update = true;", " }", " }", " if(!update)return make_pair(dist, negative);", " }", "", " for(int i = 0; i < V; i++){", " for(auto &e : edges){", " ll weight;", " int now, nxt;", " tie(weight, now, nxt) = e;", " if(dist[now] != LINF && dist[nxt] > dist[now] + weight){", " dist[nxt] = dist[now] + weight;", " negative[nxt] = true;", " }", " if(negative[now]) negative[nxt] = true;", " }", " }", "", " return make_pair(dist, negative);", "}", "" ], "description": "bellman_ford" }, "warshall_floyd": { "prefix": "atcoder_graph_warshall_floyd", "body": [ "void warshall_floyd(vector> &dist){", " int N = dist.size();", " for(int i=0;i topological_sort(Graph &g){", " int N = g.size();", " vector deg(N);", " for(int from_=0;from_ que;", " rep(i,N){", " if (deg[i] == 0) que.push(i);", " }", " vector res;", " while(!que.empty()){", " auto now = que.front(); que.pop();", " res.push_back(now);", " for(auto nxt:g[now]){", " deg[nxt]--;", " if (deg[nxt] == 0){", " que.push(nxt);", " }", " }", " }", " return res;", "}", "" ], "description": "topological_sort" }, // // tree algorithm // "LCT": { "prefix": "atcoder_tree_LinkCutTree", "body": [ "", "// https://judge.yosupo.jp/submission/206333", "//【Link-Cut Tree（可換モノイド）】", "/*", "* Link_cut_tree(int n) : O(n)", "* 値 o() をもった n 頂点で初期化する．", "* 要素は可換モノイド (S, op, o) の元とする．", "*", "* Link_cut_tree(vS a) : O(n log n)", "* 値 a[0..n) をもった n 頂点で初期化する．", "*", "* cut(int i) : ならし O(log n)", "* 頂点 i とその親との間の辺を切断する．", "* 制約：i は根でない．", "*", "* cut(int s, int t) : ならし O(log n)", "* 辺 s-t を切断する（辺がなければ何もしない）", "*", "* link(int s, int t) : ならし O(log n)", "* 頂点 s と根 t に対し，親から子への辺 s→t を繋ぐ．", "* 制約：t は根である．", "*", "* set_root(int rt) : ならし O(log n)", "* 頂点 rt を根にする．", "*", "* S sum(int i) : ならし O(log n)", "* 根から頂点 i まで（両端含む）の頂点の値の総和を返す．", "*", "* set(int i, S x) : ならし O(log n)", "* 頂点 i の値を x に変更する．", "*", "* add(int i, S x) : ならし O(log n)", "* 頂点 i の値に x を加える．", "*", "* bool connectedQ(int s, int t) : ならし O(log n)", "* 頂点 s, t が連結かを返す．", "*/", "template ", "class Link_cut_tree {", " // 参考 : https://www.slideshare.net/iwiwi/2-12188845", " // 参考 : https://ei1333.github.io/library/structure/lct/link-cut-tree.hpp.html", "", " // splay 木（平衡二分探索木）のノード", " // key は Link-Cut 木のノードの深さとし，左ほど浅く右ほど深いものとする．", " struct Node {", " S val; // 頂点の値", " S acc; // 部分木のノードの総和", " bool rev; // 部分木が反転されているか", " Node* p; // 親へのポインタ（heavy path 内部または外部）", " Node* l, * r; // 左右の子へのポインタ", "", " Node(S val = o()) : val(val), acc(val), rev(false), p(nullptr), l(nullptr), r(nullptr) {}", "", " // 自身が根かを返す．", " bool rootQ() {", " // 親が設定されていなければもちろん根である．", " // そうでなくてもそれが heavy path 外部の親であれば自身は根である．", " return !p || (p->l != this && p->r != this);", " }", "", " // 自身の情報を子の情報をもとにして更新する．", " void pushup() {", " acc = op(l ? l->acc : o(), op(val, r ? r->acc : o()));", " }", "", " void pushdown() {", " // 反転フラグが立っていたら実際に反転しフラグを折る．", " if (rev) {", " rev = false;", " swap(l, r);", "", " // 自分の子については反転フラグを flip しておくだけにする．", " if (l) l->rev = !l->rev;", " if (r) r->rev = !r->rev;", " }", "", " // 自身の情報（acc）を子の情報をもとにして更新する．", " pushup();", " }", "", " // 右回転する．", " void rotR() {", " Node* my_p = p, * my_pp = my_p->p;", "", " // 自分の親と自分の右の子（あれば）を繋ぐ．", " if (my_p->l = r) r->p = my_p;", " my_p->pushup();", "", " // 自身と自分の親の親子関係を逆転させる．", " r = my_p; my_p->p = this;", " pushup();", "", " // 自身と自分の親の親（あれば）を繋ぐ．", " if (p = my_pp) {", " if (my_pp->l == my_p) my_pp->l = this;", " if (my_pp->r == my_p) my_pp->r = this;", " }", " }", "", " // 左回転する．", " void rotL() {", " Node* my_p = p, * my_pp = my_p->p;", "", " // 自分の親と自分の左の子（あれば）を繋ぐ．", " if (my_p->r = l) l->p = my_p;", " my_p->pushup();", "", " // 自身と自分の親の親子関係を逆転させる．", " l = my_p; my_p->p = this;", " pushup();", "", " // 自身と自分の親の親（あれば）を繋ぐ．", " if (p = my_pp) {", " if (my_pp->l == my_p) my_pp->l = this;", " if (my_pp->r == my_p) my_pp->r = this;", " }", " }", "", " // 自身を heavy path 内の根に持ってくる（スプレー操作）", " void splay() {", " pushdown();", "", " // 自身が根でないかぎり操作を続ける．", " while (!rootQ()) {", " Node* my_p = p;", "", " // 自分の親が根である場合", " if (my_p->rootQ()) {", " my_p->pushdown();", " pushdown();", "", " // 適切な回転操作を行う．", " if (my_p->l == this) rotR();", " else rotL();", " }", " // 自分の親が根でない場合", " else {", " Node* my_pp = my_p->p;", " my_pp->pushdown();", " my_p->pushdown();", " pushdown();", "", " // 自分の親の親から自分まで同方向に枝が伸びている場合は zig-zig ステップ，", " // さもなくば zig-zag ステップを実行する．", " if (my_pp->l == my_p) {", " // zig-zig ステップ", " if (my_p->l == this) my_p->rotR(), rotR();", " // zig-zag ステップ", " else rotL(), rotR();", " }", " else {", " // zig-zig ステップ", " if (my_p->r == this) my_p->rotL(), rotL();", " // zig-zag ステップ", " else rotR(), rotL();", " }", " }", " }", " }", " };", "", " int n; // 頂点数", " vector vs; // 頂点のリスト", "", " // 木の根から頂点 v までを 1 つの heavy path にし，v を heavy path 内の根とする．", " void expose(Node* v) {", " auto v0(v);", "", " // rt : 作成途中の heavy path の根", " Node* rt = nullptr;", "", " while (v) {", " // v をいまの heavy path 内の根にもってくる．", " v->splay();", "", " // v の右の子を切り離し，作成途中の heavy path を繋ぐ．", " v->r = rt;", " rt = v;", " v->pushup();", "", " // 1 つ上の heavy path に移動する．", " v = v->p;", " }", "", " // v を構築した heavy path 内の根とする．", " v0->splay();", " }", "", " // 頂点 v とその親との間の辺を切断する．", " void cut(Node* v) {", " // 木の根から v までの heavy path を繋ぐ．", " expose(v);", "", " // v の親は v より 1 つ浅いので v の左の子孫になっている．", " Node* l = v->l;", "", " // v とその親の間の辺を切断する．", " v->l = nullptr;", " l->p = nullptr;", "", " v->pushup();", " }", "", " // 頂点 v, vp を繋ぎ，v の親を vp とする（v は根であること）", " void link(Node* v, Node* vp) {", " // それぞれの木の根から v, vp までの heavy path を繋ぐ．", " expose(v);", " expose(vp);", "", " // vp と v の間の辺を繋ぐ（v の方が深いので v を vp の右の子とする）", " v->p = vp;", " vp->r = v;", "", " vp->pushup();", " }", "", " // 頂点 v を木の根にする．", " void evert(Node* v) {", " expose(v);", " v->rev = !v->rev;", " }", "", "public:", " // 値 o() をもった n 頂点で初期化する．", " Link_cut_tree(int n) : n(n), vs(n) { }", "", " // 値 a[0..n) をもった n 頂点で初期化する．", " Link_cut_tree(const vector& a) : n((int)a.size()), vs(n) {", " // verify : https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum", "", " rep(i, n) vs[i].val = vs[i].acc = a[i];", " }", "", " // 頂点 i とその親との間の辺を切断する．", " void cut(int i) {", " cut(&vs[i]);", " }", "", " // 辺 s-t を切断する（なければ何もしない）", " void cut(int s, int t) {", " // verify : https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum", "", " if (s == t) return;", " expose(&vs[s]), expose(&vs[t]);", " if (!vs[s].p) return;", "", " if (vs[t].l == &vs[s]) {", " Node* l = vs[t].l;", " vs[t].l = nullptr;", " l->p = nullptr;", " vs[t].pushup();", " }", " else {", " expose(&vs[s]);", " Node* l = vs[s].l;", " vs[s].l = nullptr;", " l->p = nullptr;", " vs[s].pushup();", " }", " }", "", " // 頂点 s と根 t に対し，親から子への辺 s→t を繋ぐ．", " void link(int s, int t) {", " // verify : https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum", "", " link(&vs[t], &vs[s]);", " }", "", " // 頂点 rt を根にする．", " void set_root(int rt) {", " // verify : https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum", "", " evert(&vs[rt]);", " }", "", " // 根から頂点 i まで（両端含む）の頂点の値の総和を返す．", " S sum(int i) {", " // verify : https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum", "", " expose(&vs[i]);", " return vs[i].acc;", " }", "", " // 頂点 i の値を x に変更する．", " void set(int i, S x) {", " expose(&vs[i]);", " vs[i].val = x;", " vs[i].pushup();", " }", "", " // 頂点 i の値に x を加える．", " void add(int i, S x) {", " // verify : https://judge.yosupo.jp/problem/dynamic_tree_vertex_add_path_sum", "", " expose(&vs[i]);", " vs[i].val = op(x, vs[i].val);", " vs[i].pushup();", " }", "", " // 頂点 s, t が連結かを返す．", " bool connectedQ(int s, int t) {", " // verify : https://atcoder.jp/contests/abc350/tasks/abc350_g", "", " if (s == t) return true;", " expose(&vs[s]), expose(&vs[t]);", " return vs[s].p;", " }", "", "#ifdef _MSC_VER", " friend ostream& operator<<(ostream& os, Link_cut_tree LCT) {", " rep(i, LCT.n) {", " LCT.set_root(i);", " os << LCT.sum(i) << \" \";", " }", " return os;", " }", "#endif", "};" ], "description": "LCT" }, "LCA": { "prefix": "atcoder_tree_LCA", "body": [ "//https://algo-logic.info/lca/", "struct LCA{", " vector> doubling; //doubling[k][u]...頂点uからpow(2,k)遡った頂点番号", " vector dist; //dist[u]...頂点uからrootまでの距離", " LCA(const Graph &G , int root = 0){ init(G,root) ;}", " ", " void init(const Graph &G , int root = 0){", " int N = G.size();", " int logN = 1;", " while((1<(N,-1));", " dist.assign(N,-1);;", " dfs(G,root,-1,0);", " for (int k=0;k> k & 1){", " u = doubling[k][u];", " }", " }", " if (u == v) return u;", " for (int k=logN-1;k>=0;k--){", " if (doubling[k][u] != doubling[k][v]){", " u = doubling[k][u];", " v = doubling[k][v];", " }", " }", " return doubling[0][u];", " }", " int get_dist(int u,int v){", " return dist[u] + dist[v] - 2 * dist[query(u,v)];", " }", " bool is_on_path(int u,int v, int target){", " return get_dist(u,v) == get_dist(u,target) + get_dist(target,v);", " }", "};" ], "description": "LCA" }, "HLD": { "prefix": "atcoder_tree_hld", "body": [ "// HL-Decomposition", "// vid: id of v after HL-Decomposition", "// inv: inv[vid[v]] = v", "// par: id of parent", "// depth", "// subsize: size of subtree", "// head: head-id in the heavy-path", "// prev, next: prev-id, next-id in the heavy-path", "// type: the id of tree for forest", "// vend: the last-id of node in v-subtree", "typedef vector > Graph;", "struct HLDecomposition {", " int n;", " Graph G;", " vector vid, inv, par, depth, subsize, head, prev, next, type;", " ", " // construct", " HLDecomposition() { }", " HLDecomposition(const Graph &G_) :", " n((int)G_.size()), G(G_),", " vid(n, -1), inv(n), par(n), depth(n), subsize(n, 1),", " head(n), prev(n, -1), next(n, -1), type(n) { }", " void build(vector roots = {0}) {", " int curtype = 0, pos = 0;", " for (auto r : roots) decide_heavy_edge(r), reconstruct(r, curtype++, pos);", " }", " void decide_heavy_edge(int r) {", " stack > st;", " par[r] = -1, depth[r] = 0;", " st.emplace(r, 0);", " while (!st.empty()) {", " int v = st.top().first;", " int &i = st.top().second;", " if (i < (int)G[v].size()) {", " int e = G[v][i++];", " if (e == par[v]) continue;", " par[e] = v, depth[e] = depth[v] + 1;", " st.emplace(e, 0);", " }", " else {", " st.pop();", " int maxsize = 0;", " for (auto e : G[v]) {", " if (e == par[v]) continue;", " subsize[v] += subsize[e];", " if (maxsize < subsize[e]) maxsize = subsize[e], prev[e] = v, next[v] = e;", " }", " }", " }", " }", " void reconstruct(int r, int curtype, int &pos) {", " stack st({r});", " while (!st.empty()) {", " int start = st.top(); st.pop();", " for (int v = start; v != -1; v = next[v]) {", " type[v] = curtype;", " vid[v] = pos++;", " inv[vid[v]] = v;", " head[v] = start;", " for (auto e : G[v]) if (e != par[v] && e != next[v]) st.push(e);", " }", " }", " }", " ", " // node query [u, v], f([left, right])", " void foreach_nodes(int u, int v, const function &f) {", " while (true) {", " if (vid[u] > vid[v]) swap(u, v);", " f(max(vid[head[v]], vid[u]), vid[v]);", " if (head[u] != head[v]) v = par[head[v]];", " else break;", " }", " }", " ", " // edge query [u, v], f([left, right])", " void foreach_edges(int u, int v, const function &f) {", " while (true) {", " if (vid[u] > vid[v]) swap(u, v);", " if (head[u] != head[v]) {", " f(vid[head[v]], vid[v]);", " v = par[head[v]];", " }", " else {", " if (u != v) {", " f(vid[u]+1, vid[v]);", " }", " break;", " }", " }", " }", "", " // https://atcoder.jp/contests/abc138/submissions/38833623", " void subtree_nodes(int v, const function &f) {", " f(vid[v],vid[v]+subsize[v]);", " }", "", " // https://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=7464630#1", " void subtree_edges(int v, const function &f) {", " f(vid[v] + 1, vid[v] + subsize[v]);", " }", "", " // LCA", " int lca(int u, int v) {", " while (true) {", " if (vid[u] > vid[v]) swap(u, v);", " if (head[u] == head[v]) return u;", " v = par[head[v]];", " }", " }", "};", "// https://drken1215.hatenablog.com/entry/2018/08/14/193500", "// HLDecomposition hld(g);", "// hld.build();", "//", "// [path_query]", "// hld.foreach_nodes(v, u, [&](int l, int r) {seg.apply(l,r+1,x);});", "// hld.foreach_edges(v, u, [&](int l, int r) {ans += seg.prod(l,r+1,x);}); // range sum", "// hld.foreach_edges(v, u, [&](int l, int r) {ans = max(ans, seg.prod(l,r+1,x));}); // range max", "//", "// [subtree_query]", "// hld.subtree_nodes(v,[&](int l, int r) {seg.apply(l,r,x);});", "// hld.subtree_edges(v,[&](int l, int r) {seg.apply(l,r,x);});", "// ", "// 頂点iに対応するid -> hld.vid[i]", "// ex) 頂点iの値を変更 -> seg.set(hld.vid[i], A[i])" ], "description": "HLD" }, "rerooting": { "prefix": "atcoder_tree_rerooting", "body": [ "template", "struct RerootingDP {", " struct edge{", " int from, to, idx, rev_idx;", " };", " RerootingDP (int _n = 0) : n(_n) { es.resize(n);}", " void add_edge(int u, int v, int idx1, int idx2){", " es[u].push_back({u,v,idx1,idx2});", " es[v].push_back({v,u,idx2,idx1});", " }", " V build(int v = 0){", " root = v;", " vis.resize(n,0);", " outs.resize(n);", " return dfs(root);", " }", " vector reroot(){", " reverse_edge.resize(n);", " reverse_edge[root] = e();", " answers.resize(n);", " bfs(root);", " return answers;", " }", " private:", " int n, root;", " vector> es;", " vector vis;", " vector> outs;", " vector reverse_edge;", " vector answers;", " V dfs(int v){", " vis[v]++;", " E val = e();", " for (auto &p : es[v]){", " if (vis[p.to] > 0 && p.to != es[v].back().to) swap(p,es[v].back());", " if (vis[p.to] > 0) continue;", " E nval = put_edge(dfs(p.to),p.idx);", " outs[v].emplace_back(nval);", " val = merge(val,nval);", " }", " return put_vertex(val,v);", " }", " void bfs(int v){", " int siz = outs[v].size();", " vector lui(siz+1), rui(siz+1);", " lui[0] = e(), rui[siz] = e();", " for (int i = 0; i < siz; i++) lui[i+1] = merge(lui[i],outs[v][i]);", " for (int i = siz-1; i >= 0; i--) rui[i] = merge(outs[v][i],rui[i+1]);", " for (int i = 0; i < siz; i++){", " reverse_edge[es[v][i].to] = put_edge(put_vertex(merge(merge(lui[i],rui[i+1]),reverse_edge[v]),v),es[v][i].rev_idx);", " bfs(es[v][i].to);", " }", " answers[v] = put_vertex(merge(lui[siz],reverse_edge[v]), v);", " }", "};", "", "// Education dp subtree", "// https://atcoder.jp/contests/dp/submissions/37662999", "using T_monoid = mint; // E", "using T_DP = mint; // V", "", "T_monoid merge(T_monoid a, T_monoid b){", " return a * b;", "}", "T_monoid e(){", " return mint(1);", "}", "T_monoid put_edge(T_DP x, int i){", " return x + 1;", "}", "T_DP put_vertex(T_monoid x, int v){", " return x;", "}", "// 参考", "// https://trap.jp/post/1702/", "", "// https://null-mn.hatenablog.com/entry/2020/04/14/124151 ", "// fがput_edge, gがput_vertex", "// 辺の情報が必要なときはedge[i]を作る、また頂点の情報が必要な時はvertex[v]を作る", "" ], "description": "rerooting" }, // // string algorithm // "toint": { "prefix": "atcoder_string_toint", "body": [ "struct string_converter {", " char start = 0;", " char type(const char &c) const { return (islower(c) ? 'a' : isupper(c) ? 'A' : isdigit(c) ? '0' : 0); }", " int convert(const char &c) {", " if(!start) start = type(c);", " return c - start;", " }", " int convert(const char &c, const string &chars) { return chars.find(c); }", " template auto convert(const T &v) {", " vector ret;", " ret.reserve(v.size());", " for(auto &&e : v) ret.emplace_back(convert(e));", " return ret;", " }", " template auto convert(const T &v, const string &chars) {", " vector ret;", " ret.reserve(v.size());", " for(auto &&e : v) ret.emplace_back(convert(e, chars));", " return ret;", " }", " int operator()(const char &v, char s = 0) {", " start = s;", " return convert(v);", " }", " int operator()(const char &v, const string &chars) { return convert(v, chars); }", " template auto operator()(const T &v, char s = 0) {", " start = s;", " return convert(v);", " }", " template auto operator()(const T &v, const string &chars) { return convert(v, chars); }", "} toint;", "https://twitter.com/noimi_kyopro/status/1613160018769252361", "// cout << toint('1') << endl; // 1", "// cout << toint('a') << endl; // 0", "// cout << toint('A') << endl; // 0", "// cout << toint('B') << endl; // 1", "// string MOJI = \"ABC123abc\";", "// for(auto x:MOJI) cout << toint(x) << endl; // 0 1 2 1 2 3 0 1 2", "// vector c = toint(MOJI);", "// for(auto x:c) cout << x << endl; // 0 1 2 -16 -15 -14 32 33 34", "// cout << toint('#',\"#.\") << endl; // 0", "// cout << toint('.',\"#.\") << endl; // 1", "" ], "description": "toint" }, "rolling_hash": { "prefix": "atcoder_string_rollinghash", "body": [ "struct RollingHash{", " static const int B = 3;", " long long base[B] = {114514, 1919, 810};", " long long mod[B] = {1000000007, 1000000009, 998244353};", "", " int N;", " vector> hash;", " vector> pw;", " RollingHash(string &S){", " N = S.size();", " hash.resize(B);", " pw.resize(B);", " for(int b = 0; b < B; b++){", " hash[b].resize(N + 1, 0);", " pw[b].resize(N + 1, 1);", "", " for(int i = 0; i < N; i++){", " hash[b][i + 1] = (hash[b][i] * base[b] + S[i]) % mod[b];", " pw[b][i + 1] = pw[b][i] * base[b] % mod[b];", " }", " }", " }", "", " vector get(int l, int r){", " vector res(B);", " for(int b = 0; b < B; b++){", " res[b] = (hash[b][r] - (hash[b][l] * pw[b][r - l]) % mod[b] + mod[b]) % mod[b];", " }", " return res;", " }", "", " int LCP(int l1, int r1, int l2, int r2){", " // O(log|S|)", " // return LCP between S[l1, r1) and S[l2, r2)", " int len = min(r1 - l1, r2 - l2);", " int ok = -1, ng = len + 1;", " while(abs(ok - ng) > 1){", " int mid = (ok + ng) / 2;", " if (get(l1, l1 + mid) == get(l2, l2 + mid)) ok = mid;", " else ng = mid;", " }", " return ok;", " }", "};", "" ], "description": "rolling_hash" }, "Trie": { "prefix": "atcoder_string_trie", "body": [ "//https://algo-logic.info/trie-tree/", "/* Trie 木： 文字の種類(char_size)、int型で0に対応する文字(base)", " insert(word): 単語 word を Trie 木に挿入する", " search(word): 単語 word が Trie 木にあるか判定する", " start_with(prefix): prefix が一致する単語が Trie 木にあるか判定する", " count(): 挿入した単語の数を返す", " size(): Trie 木の頂点数を返す", " 計算量：insert, search ともに O(M)（Mは単語の長さ）", "*/", "template ", "struct Trie {", " struct Node { // 頂点を表す構造体", " vector next; // 子の頂点番号を格納。存在しなければ-1", " vector accept; // 末端がこの頂点になる単語の word_id を保存", " int c; // base からの間隔をint型で表現したもの", " int common; // いくつの単語がこの頂点を共有しているか", " Node(int c_) : c(c_), common(0) {", " next.assign(char_size, -1);", " }", " };", "", " vector nodes; // trie 木本体", " int root;", " Trie() : root(0) {", " nodes.push_back(Node(root));", " }", "", " // 単語の挿入", " void insert(const string &word, int word_id) {", " int node_id = 0;", " for (int i = 0; i < (int)word.size(); i++) {", " int c = (int)(word[i] - base);", " int &next_id = nodes[node_id].next[c];", " if (next_id == -1) { // 次の頂点が存在しなければ追加", " next_id = (int)nodes.size();", " nodes.push_back(Node(c));", " }", " ++nodes[node_id].common;", " node_id = next_id;", " }", " ++nodes[node_id].common;", " nodes[node_id].accept.push_back(word_id);", " }", " void insert(const string &word) {", " insert(word, nodes[0].common);", " }", "", " // 単語とprefixの検索", " bool search(const string &word, bool prefix = false) {", " int node_id = 0;", " for (int i = 0; i < (int)word.size(); i++) {", " int c = (int)(word[i] - base);", " int &next_id = nodes[node_id].next[c];", " if (next_id == -1) { // 次の頂点が存在しなければ終了", " return false;", " }", " node_id = next_id;", " }", " return (prefix) ? true : nodes[node_id].accept.size() > 0;", " }", "", " // prefix を持つ単語が存在するかの検索", " bool start_with(const string &prefix) {", " return search(prefix, true);", " }", "", " // 挿入した単語の数", " int count() const {", " return (nodes[0].common);", " }", " // Trie木のノード数 , ただしrootも含む", " int size() const {", " return ((int)nodes.size());", " }", " ", " // node_id = tmpの下に文字c(c = 0,1,..25)で終わる文字があるか", " bool match(int tmp, int c){", " int nxt_id = nodes[tmp].next[c];", " return (nxt_id != -1) && (nodes[nxt_id].accept.size() > 0);", " }", "};", "//Trie<26,'a'> trie;", "", "" ], "description": "Trie" }, // // AHC // "ahc_main": { "prefix": "atcoder_ahc_main", "body": [ "#include ", "#include ", "using namespace std;", "using namespace atcoder;", "istream &operator>>(istream &is, modint &a) { long long v; is >> v; a = v; return is; }", "ostream &operator<<(ostream &os, const modint &a) { return os << a.val(); }", "istream &operator>>(istream &is, modint998244353 &a) { long long v; is >> v; a = v; return is; }", "ostream &operator<<(ostream &os, const modint998244353 &a) { return os << a.val(); }", "istream &operator>>(istream &is, modint1000000007 &a) { long long v; is >> v; a = v; return is; }", "ostream &operator<<(ostream &os, const modint1000000007 &a) { return os << a.val(); }", "", "typedef long long ll;", "typedef pair pii;", "typedef pair pll;", "#define FOR(i,l,r) for (int i = l;i < (int)(r); i++)", "#define rep(i,n) for (int i = 0;i < (int)(n); i++)", "#define all(x) x.begin(), x.end()", "template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }", "template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }", "", "#ifdef LOCAL", " #include ", " #define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__)", "#else", " #define debug(...) (static_cast(0))", "#endif", "", "// https://github.com/thun-c/thunder_library/blob/main/thunder/lib/timer.cpp", "/// 軽量な実行時間計測器。", "/// `reset()` で計測開始を更新し、`elapsed()` で経過秒(float)を返す。", "struct Timer {", " chrono::steady_clock::time_point t_begin;", "", " Timer() { reset(); }", "", " /// 計測開始時刻を現在時刻に戻す。", " void reset() { t_begin = chrono::steady_clock::now(); }", "", " /// 計測開始からの経過時間を秒で返す。", " float elapsed() const {", " return chrono::duration(chrono::steady_clock::now() - t_begin).count();", " }", "} timer;", "", "// https://atcoder.jp/contests/ahc063/submissions/74942932", "struct RNG {", " uint64_t s[2];", " RNG(uint64_t seed) { reset(seed); }", " RNG() { reset(time(0)); }", " using result_type = uint32_t;", " static constexpr uint32_t min() { return numeric_limits::min(); }", " static constexpr uint32_t max() { return numeric_limits::max(); }", " uint32_t operator()() { return randomInt32(); }", " static inline uint64_t rotl(const uint64_t x, int k) { return (x << k) | (x >> (64 - k)); }", " inline void reset(uint64_t seed) {", " struct splitmix64_state {", " uint64_t s;", " uint64_t splitmix64() {", " uint64_t result = (s += 0x9E3779B97f4A7C15);", " result = (result ^ (result >> 30)) * 0xBF58476D1CE4E5B9;", " result = (result ^ (result >> 27)) * 0x94D049BB133111EB;", " return result ^ (result >> 31);", " }", " };", " splitmix64_state sm{seed};", " s[0] = sm.splitmix64();", " s[1] = sm.splitmix64();", " }", " uint64_t next() {", " const uint64_t s0 = s[0];", " uint64_t s1 = s[1];", " const uint64_t result = rotl(s0 * 5, 7) * 9;", " s1 ^= s0;", " s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16);", " s[1] = rotl(s1, 37);", " return result;", " }", " inline uint32_t randomInt32() { return next(); }", " inline uint64_t randomInt64() { return next(); }", " inline uint32_t random32(uint32_t r) { return (((uint64_t)randomInt32()) * r) >> 32; }", " inline uint64_t random64(uint64_t r) { return randomInt64() % r; }", " inline uint32_t randomRange32(uint32_t l, uint32_t r) { return l + random32(r - l + 1); }", " inline uint64_t randomRange64(uint64_t l, uint64_t r) { return l + random64(r - l + 1); }", " inline double randomDouble() { return (double)randomInt32() / 4294967296.0; }", " inline double randomDoubleOpen01() { return (randomInt32() + 1.0) / 4294967297.0; }", " inline float randomFloat() { return (float)randomInt32() / 4294967296.0; }", " inline double randomRangeDouble(double l, double r) { return l + randomDouble() * (r - l); }", " inline double randomGaussian(double mean = 0.0, double stddev = 1.0) {", " double u1 = randomDoubleOpen01();", " double u2 = randomDouble();", " double z = sqrt(-2.0 * log(u1)) * cos(2.0 * 3.141592653589793238 * u2);", " return mean + stddev * z;", " }", " template void shuffle(vector& v) {", " int sz = v.size();", " for (int i = sz; i > 1; i--) swap(v[i - 1], v[random32(i)]);", " }", " template void shuffle(T* fr, T* to) {", " int sz = distance(fr, to);", " for (int i = sz; i > 1; i--) swap(fr[i - 1], fr[random32(i)]);", " }", " template inline int sample_index(vector const& v) { return random32(v.size()); }", " template inline T sample(vector const& v) { return v[sample_index(v)]; }", "} rng(42);", "", "struct Input {", " void input() {", " }", "};", "", "struct Solver {", " const Input& input;", "", " explicit Solver(const Input& input) : input(input) {}", "", " void solve() {", " timer.reset();", " }", "", " void print() const {", " }", "};", "", "int main() {", " ios::sync_with_stdio(false);", " cin.tie(nullptr);", "", " Input input;", " input.input();", "", " Solver solver(input);", " solver.solve();", " solver.print();", " return 0;", "}", "" ], "description": "ahc_main" }, "fastset": { "prefix": "atcoder_ahc_fastset", "body": [ "// 整数集合 [0, n) に対する insert/erase/next/prev が O(log n / log 64) の 64 分木。", "// std::set より高速。", "//", "// Usage:", "// FastSet fs(N);", "// fs.insert(i);", "// fs.erase(i);", "// fs.contains(i); // O(1)", "// fs.next(i); // i 以上の最小値。なければ N。", "// fs.prev(i); // i 以下の最大値。なければ -1。", "// fs.min_val(); // 最小値", "// fs.max_val(); // 最大値", "// fs.empty();", "struct FastSet {", " static constexpr int B = 64;", " int n_, log_;", " vector> d_;", "", " FastSet() : n_(0), log_(0) {}", " explicit FastSet(int n) : n_(n), log_(0) {", " if (n == 0) return;", " int m = n;", " do {", " d_.push_back(vector((m + B - 1) / B, 0));", " m = (m + B - 1) / B;", " } while (m > 1);", " log_ = (int)d_.size();", " }", "", " void insert(int i) {", " for (int h = 0; h < log_; h++) {", " d_[h][i / B] |= 1ULL << (i % B);", " i /= B;", " }", " }", "", " void erase(int i) {", " for (int h = 0; h < log_; h++) {", " d_[h][i / B] &= ~(1ULL << (i % B));", " if (d_[h][i / B]) break;", " i /= B;", " }", " }", "", " bool contains(int i) const { return (d_[0][i / B] >> (i % B)) & 1; }", " bool empty() const { return d_[log_ - 1][0] == 0; }", "", " // i 以上の最小値。なければ n_ を返す。", " int next(int i) const {", " for (int h = 0; h < log_; h++) {", " int b = i / B;", " if (b >= (int)d_[h].size()) break;", " uint64_t f = d_[h][b] >> (i % B);", " if (!f) { i = b + 1; continue; }", " i += __builtin_ctzll(f);", " for (int g = h - 1; g >= 0; g--)", " i = i * B + __builtin_ctzll(d_[g][i]);", " return i;", " }", " return n_;", " }", "", " // i 以下の最大値。なければ -1 を返す。", " int prev(int i) const {", " for (int h = 0; h < log_; h++) {", " if (i < 0) break;", " int b = i / B;", " uint64_t f = d_[h][b] << (B - 1 - i % B);", " if (!f) { i = b - 1; continue; }", " i -= __builtin_clzll(f);", " for (int g = h - 1; g >= 0; g--)", " i = i * B + 63 - __builtin_clzll(d_[g][i]);", " return i;", " }", " return -1;", " }", "", " int min_val() const { return next(0); }", " int max_val() const { return prev(n_ - 1); }", "};" ], "description": "fastset" }, "hashmap": { "prefix": "atcoder_ahc_hashmap", "body": [ "// open addressing, linear probing。unordered_map より高速。", "// Key にはハッシュ適用済みの値を渡す。n は格納要素数の 16 倍程度。", "// clear() は O(1)（stamp インクリメントのみ）。", "//", "// Usage:", "// HashMap seen(beam_width * 16);", "// auto [exists, idx] = seen.get_index(hash);", "// if (!exists) seen.set(idx, hash, node_id);", "// int v = seen.get(idx);", "// seen.clear(); // 次ターンへ O(1)", "template", "struct HashMap {", " uint32_t n_;", " uint32_t current_stamp_ = 1;", " vector stamp_;", " vector> data_;", "", " explicit HashMap(uint32_t n) {", " if (n % 2 == 0) ++n;", " n_ = n;", " stamp_.assign(n_, 0);", " data_.resize(n_);", " }", "", " // {存在するか, index} を返す。set/get には index を使う。", " pair get_index(Key key) const {", " uint32_t i = (uint32_t)(key % n_);", " while (stamp_[i] == current_stamp_) {", " if (data_[i].first == key) return {true, (int)i};", " if (++i == n_) i = 0;", " }", " return {false, (int)i};", " }", "", " void set(int i, Key key, T value) {", " stamp_[i] = current_stamp_;", " data_[i] = {key, value};", " }", "", " T get(int i) const { return data_[i].second; }", "", " void clear() {", " if (++current_stamp_ == 0) {", " fill(stamp_.begin(), stamp_.end(), 0);", " current_stamp_ = 1;", " }", " }", "};" ], "description": "hashmap" }, "conntable": { "prefix": "atcoder_ahc_conntable", "body": [ "// 3x3 局所連結性テーブル。8近傍ビットマスク（256通り）の連結成分数を事前計算。", "// conn8=true で8連結（斜め隣接あり）、false で4連結（上下左右のみ）。", "//", "// 近傍ビット配置:", "// 0 1 2", "// 3 C 4", "// 5 6 7", "//", "// Usage:", "// ConnTable<> ct; // 8連結（デフォルト）", "// ConnTable ct; // 4連結", "// uint8_t mask = ct.neighbors(grid, r, c, H, W); // grid[r][c] が 0/1 の2次元配列", "// int comp = ct.components(mask); // 中心セルを除いた連結成分数", "// bool safe = ct.can_remove(mask); // 削除しても連結性が保たれるか", "//", "// // 典型: セル(r,c)を安全に削除できるか確認して消す", "// if (ct.can_remove(ct.neighbors(grid, r, c, H, W))) grid[r][c] = 0;", "template", "struct ConnTable {", " uint8_t table[256];", "", " ConnTable() {", " for (int mask = 0; mask < 256; mask++)", " table[mask] = count_components(mask);", " }", "", " int components(uint8_t mask) const { return table[mask]; }", " bool can_remove(uint8_t mask) const { return table[mask] <= 1; }", "", " template", " uint8_t neighbors(const Grid& grid, int r, int c, int H, int W) const {", " static const int dr[] = {-1,-1,-1, 0, 0, 1, 1, 1};", " static const int dc[] = {-1, 0, 1,-1, 1,-1, 0, 1};", " uint8_t mask = 0;", " for (int k = 0; k < 8; k++) {", " int nr = r + dr[k], nc = c + dc[k];", " if (nr >= 0 && nr < H && nc >= 0 && nc < W && grid[nr][nc])", " mask |= 1 << k;", " }", " return mask;", " }", "", "private:", " static int count_components(int mask) {", " static const int adj8[8][4] = {", " {1, 3, -1, -1}, // 0", " {0, 2, 3, 4}, // 1", " {1, 4, -1, -1}, // 2", " {0, 1, 5, 6}, // 3", " {1, 2, 6, 7}, // 4", " {3, 6, -1, -1}, // 5", " {3, 4, 5, 7}, // 6", " {4, 6, -1, -1}, // 7", " };", " static const int adj4[8][4] = {", " {1, 3, -1, -1}, // 0", " {0, 2, -1, -1}, // 1", " {1, 4, -1, -1}, // 2", " {0, 5, -1, -1}, // 3", " {2, 7, -1, -1}, // 4", " {3, 6, -1, -1}, // 5", " {5, 7, -1, -1}, // 6", " {4, 6, -1, -1}, // 7", " };", " const auto& adj = conn8 ? adj8 : adj4;", " int comp = 0;", " uint8_t visited = 0;", " for (int i = 0; i < 8; i++) {", " if (!((mask >> i) & 1) || (visited >> i) & 1) continue;", " comp++;", " uint8_t stk = 1 << i;", " visited |= 1 << i;", " while (stk) {", " int u = __builtin_ctz(stk);", " stk &= stk - 1;", " for (int k = 0; k < 4 && adj[u][k] != -1; k++) {", " int v = adj[u][k];", " if (((mask >> v) & 1) && !((visited >> v) & 1)) {", " visited |= 1 << v;", " stk |= 1 << v;", " }", " }", " }", " }", " return comp;", " }", "};", "ConnTable<> conn_table; // 8連結。4連結が必要なら ConnTable を別途宣言。", "" ], "description": "conntable" }, "dial": { "prefix": "atcoder_ahc_dial", "body": [ "// Dial's アルゴリズム（バケットキュー）。辺コストが小さい整数のとき priority_queue より高速。", "// 時間計算量: O(V + E + max_dist)、空間計算量: O(V + E + max_cost)", "// max_cost = 最大辺コスト（BFS なら 1）", "// max_dist = 探索する最大距離（省略時は全到達頂点を探索）", "//", "// Usage:", "// vector>> adj(N); // adj[v] = {{neighbor, weight}, ...}", "// auto dist = dial(start, N, adj, 1); // BFS: 全頂点", "// auto dist = dial(start, N, adj, max_cost); // 全頂点", "// auto dist = dial(start, N, adj, max_cost, max_dist); // 距離 max_dist 以内", "vector dial(int start, int n,", " const vector>>& adj, int max_cost, int max_dist = -1) {", " const int D = max_cost + 1;", " vector dist(n, INT_MAX);", " vector> bucket(D);", " dist[start] = 0;", " bucket[0].push_back(start);", " int pending = 1;", " for (int d = 0; pending > 0; d++) {", " int bi = d % D;", " pending -= (int)bucket[bi].size();", " for (int v : bucket[bi]) {", " if (dist[v] != d) continue;", " for (auto [u, w] : adj[v]) {", " if (dist[v] + w < dist[u]) {", " dist[u] = dist[v] + w;", " if (max_dist < 0 || dist[u] <= max_dist) {", " bucket[dist[u] % D].push_back(u);", " pending++;", " }", " }", " }", " }", " bucket[bi].clear();", " }", " return dist;", "}", "" ], "description": "dial" }, "sa": { "prefix": "atcoder_ahc_sa", "body": [ "// 焼きなまし法（Simulated Annealing）", "//", "// Usage:", "// SA sa(start_temp, end_temp, time_limit); // スコアの型を指定", "//", "// // 基本パターン", "// while (timer.elapsed() < time_limit) {", "// double temp = sa.temperature(); // 温度を1回だけ取得", "// ll diff = new_score - cur_score; // diff > 0 が悪化（コスト最小化）", "// if (sa.accept(diff, temp)) { /* 採用 */ }", "// }", "//", "// // 受理ライン（スコア計算を途中打ち切りするとき）", "// double temp = sa.temperature();", "// ll line = sa.threshold(temp); // 先に受理ラインを確定", "// ll new_score = 0;", "// for (int i = 0; i < N; i++) {", "// new_score += calc_partial(i);", "// if (new_score - cur_score > line) break; // 越えると確定したら打ち切り", "// }", "// if (new_score - cur_score <= line) { /* 採用 */ }", "//", "// // 温度スケジュール", "// sa.temperature(); // 指数（デフォルト）: 序盤に広く探索", "// sa.temperature_linear(); // 線形: シンプル", "template", "struct SA {", " double start_temp, end_temp, time_limit;", "", " // -log(U), U~Uniform(0,1) のルックアップテーブル（分位点中点法）", " struct MinusLogTable {", " static constexpr int SIZE = 1 << 12;", " double table[SIZE];", " MinusLogTable() {", " for (int i = 0; i < SIZE; i++)", " table[i] = -log((i + 0.5) / SIZE);", " }", " double operator()() const {", " return table[rng.random32(SIZE)];", " }", " } minus_log_table;", "", " // 指数温度スケジュールのルックアップテーブル（構築時に事前計算）", " struct TempTable {", " static constexpr int SIZE = 1 << 12;", " double table[SIZE];", " void init(double start_temp, double end_temp) {", " for (int i = 0; i < SIZE; i++)", " table[i] = start_temp * pow(end_temp / start_temp, (i + 0.5) / SIZE);", " }", " double operator()(double ratio) const {", " return table[min(SIZE - 1, (int)(ratio * SIZE))];", " }", " } temp_table;", "", " SA(double start_temp, double end_temp, double time_limit)", " : start_temp(start_temp), end_temp(end_temp), time_limit(time_limit) {", " temp_table.init(start_temp, end_temp);", " }", "", " double ratio() const {", " return min(1.0, (double)timer.elapsed() / time_limit);", " }", "", " double temperature() const {", " return temp_table(ratio());", " }", " double temperature_linear() const {", " return start_temp + (end_temp - start_temp) * ratio();", " }", "", " // diff <= threshold(temp) なら受理。先に1回呼んで途中打ち切りに使う。", " T threshold(double temp) const { return static_cast(temp * minus_log_table()); }", " T threshold() const { return threshold(temperature()); }", "", " // diff > 0 が悪化（コスト最小化）。threshold() と数学的に等価。", " bool accept(T diff, double temp) const {", " if (diff <= 0) return true;", " return diff <= threshold(temp);", " }", " bool accept(T diff) const {", " if (diff <= 0) return true;", " return diff <= threshold(temperature());", " }", "};" ], "description": "sa" }, "Bayes": { "prefix": "atcoder_ahc_Bayes", "body": [ "// 離散ベイズ推定器。状態 0..N-1 の事後分布を log 空間で管理する。", "// likelihood[i] = P(obs | state=i) の計算は問題依存（ノイズモデルから導く）。", "//", "// Usage:", "// BayesEstimator be(N); // 一様事前分布", "// BayesEstimator be(prior); // カスタム事前分布 prior[i] = P(state=i)", "// be.update(likelihood); // likelihood[i] = P(obs | state=i)", "// be.update_log(log_likelihood); // log尤度を直接渡す版（高速）", "// double p = be.prob(i); // P(state=i | 全観測)", "// int s = be.argmax(); // 最大事後確率の状態", "// vector ps = be.probs(); // 全確率を vector で取得", "//", "// 典型的な log 尤度の計算例（update_log に渡す）:", "// // ガウスノイズ: クエリに正規分布ノイズが乗る場合", "// for (int i = 0; i < N; i++) log_lik[i] = -(obs-expected[i])*(obs-expected[i]) / (2*sigma*sigma);", "//", "// // 二値ノイズ: 正解率 p で正しい答えが返ってくる場合", "// for (int i = 0; i < N; i++) log_lik[i] = log(obs == true_val[i] ? p : 1.0-p);", "struct BayesEstimator {", " int n;", " vector log_prob;", "", " explicit BayesEstimator(int n) : n(n), log_prob(n, -log((double)n)) {}", " explicit BayesEstimator(vector prior) : n(prior.size()), log_prob(prior.size()) {", " for (int i = 0; i < n; i++) log_prob[i] = log(prior[i]);", " normalize();", " }", "", " void update(const vector& likelihood) {", " for (int i = 0; i < n; i++) log_prob[i] += log(likelihood[i]);", " normalize();", " }", " void update_log(const vector& log_likelihood) {", " for (int i = 0; i < n; i++) log_prob[i] += log_likelihood[i];", " normalize();", " }", "", " void normalize() {", " double mx = *max_element(log_prob.begin(), log_prob.end());", " double s = 0;", " for (int i = 0; i < n; i++) s += exp(log_prob[i] - mx);", " double log_s = mx + log(s);", " for (int i = 0; i < n; i++) log_prob[i] -= log_s;", " }", "", " double prob(int i) const { return exp(log_prob[i]); }", " int argmax() const { return max_element(log_prob.begin(), log_prob.end()) - log_prob.begin(); }", " vector probs() const {", " vector p(n);", " for (int i = 0; i < n; i++) p[i] = prob(i);", " return p;", " }", "};" ], "description": "Bayes" }, } #include using namespace std; typedef long long ll; typedef pair pii; typedef pair pll; #define FOR(i,l,r) for (int i = l;i < (int)(r); i++) #define rep(i,n) for (int i = 0;i < (int)(n); i++) #define all(x) x.begin(), x.end() template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } #ifdef LOCAL #include #define debug(...) debug_print::multi_print(#__VA_ARGS__, __VA_ARGS__) #else #define debug(...) (static_cast(0)) #endif // 軽量な実行時間計測器。グローバルに timer が1つある。 // 時計を間引いて読むかは呼び出し側で決める。 // // Usage: // timer.reset(); // 計測開始時刻を現在時刻に戻す // float t = timer.elapsed(); // 計測開始からの経過時間を秒で返す // // // 基本パターン // while (timer.elapsed() < time_limit) { ... } // // // 時計の読み取りを間引く（近傍が軽くて秒間数百万回まわるとき） // if (cnt % 64 == 0 && timer.elapsed() >= time_limit) break; struct Timer { Timer() { reset(); } void reset() { t_begin = chrono::steady_clock::now(); } float elapsed() const { return chrono::duration(chrono::steady_clock::now() - t_begin).count(); } private: chrono::steady_clock::time_point t_begin; } timer; // xoroshiro128**。グローバルに rng が1つある（シード 345）。 // result_type / min() / max() / operator() を持つので、std の分布 // (uniform_int_distribution など) の engine としてもそのまま渡せる。 // // Usage: // RNG my_rng(123); // シードを指定して作る // rng.reset(42); // シードを再設定する // // // 整数 // uint32_t a = rng(); // 32bit 乱数。std の分布に渡す engine 用 // uint32_t b = rng.random32(n); // [0, n) の整数。n > 0 // uint64_t c = rng.random64(n); // [0, n) の整数（64bit）。n > 0 // uint32_t d = rng.randomRange32(l, r); // [l, r] の整数。両端を含む。l <= r // uint64_t e = rng.randomRange64(l, r); // [l, r] の整数（64bit）。両端を含む // // // 実数 // double p = rng.randomDouble(); // [0, 1) の実数 // float q = rng.randomFloat(); // [0, 1) の実数（float） // double x = rng.randomRangeDouble(l, r); // [l, r) の実数 // double g = rng.randomGaussian(mean, stddev); // 正規分布 N(mean, stddev^2)。既定は N(0, 1) // // // コンテナ // rng.shuffle(v); // vector をシャッフルする // rng.shuffle(a, a + n); // [fr, to) をシャッフルする // int i = rng.sample_index(v); // 添字を一様に選ぶ。v は非空 // auto y = rng.sample(v); // 要素を一様に選ぶ。v は非空 struct RNG { using result_type = uint32_t; static constexpr uint32_t min() { return 0; } static constexpr uint32_t max() { return numeric_limits::max(); } RNG(uint64_t seed) { reset(seed); } RNG() { reset(time(0)); } void reset(uint64_t seed) { struct splitmix64_state { uint64_t s; uint64_t splitmix64() { uint64_t result = (s += 0x9E3779B97f4A7C15); result = (result ^ (result >> 30)) * 0xBF58476D1CE4E5B9; result = (result ^ (result >> 27)) * 0x94D049BB133111EB; return result ^ (result >> 31); } }; splitmix64_state sm{seed}; s[0] = sm.splitmix64(); s[1] = sm.splitmix64(); } uint32_t operator()() { return next32(); } uint32_t random32(uint32_t r) { return (uint64_t(next32()) * r) >> 32; } uint64_t random64(uint64_t r) { return uint64_t((__uint128_t(next64()) * r) >> 64); } uint32_t randomRange32(uint32_t l, uint32_t r) { return l + random32(r - l + 1); } uint64_t randomRange64(uint64_t l, uint64_t r) { return l + random64(r - l + 1); } double randomDouble() { return double(next32()) / 4294967296.0; } float randomFloat() { return float(next32()) / 4294967296.0f; } double randomRangeDouble(double l, double r) { return l + randomDouble() * (r - l); } double randomGaussian(double mean = 0.0, double stddev = 1.0) { double u1 = (next32() + 1.0) / 4294967297.0; double u2 = randomDouble(); return mean + stddev * sqrt(-2.0 * log(u1)) * cos(2.0 * 3.141592653589793238 * u2); } template void shuffle(vector& v) { for (int i = (int)v.size(); i > 1; i--) swap(v[i - 1], v[random32(i)]); } template void shuffle(T* fr, T* to) { int sz = (int)distance(fr, to); for (int i = sz; i > 1; i--) swap(fr[i - 1], fr[random32(i)]); } template int sample_index(const vector& v) { return random32((uint32_t)v.size()); } template T sample(const vector& v) { return v[sample_index(v)]; } private: uint64_t s[2]; static uint64_t rotl(uint64_t x, int k) { return (x << k) | (x >> (64 - k)); } uint64_t next64() { const uint64_t s0 = s[0]; uint64_t s1 = s[1]; const uint64_t result = rotl(s0 * 5, 7) * 9; s1 ^= s0; s[0] = rotl(s0, 24) ^ s1 ^ (s1 << 16); s[1] = rotl(s1, 37); return result; } uint32_t next32() { return (uint32_t)next64(); } } rng(345); // 焼きなまし法（Simulated Annealing）。スコアの型 T を指定する。 // コスト最小化。スコア最大化のときは accept(cur - neu, temp) と符号を反転させる。 // end_temp は正であること（指数スケジュールの pow のため）。 // 構築時に開始時刻を1回記録する。進捗は (now - 開始) / (end_time - 開始)。 // end_time は timer.elapsed() と同じ時計での終了時刻。温度の間引きは Solver 側で行う。 // // Usage: // SA sa(start_temp, end_temp, end_time); // 例: end_time = 2.85 // // double t1 = sa.temperature(); // 指数スケジュールの温度。序盤に広く探索する // double t2 = sa.temperature_linear(); // 線形スケジュールの温度 // ll line = sa.threshold(temp); // 受理ライン。diff <= line なら受理 // bool ok = sa.accept(diff, temp); // diff > 0 が悪化。温度は呼び出し側で1回取って渡す // // // 基本パターン // while (timer.elapsed() < end_time) { // double temp = sa.temperature(); // 温度は1回だけ取る // ll diff = new_score - cur_score; // diff > 0 が悪化 // if (sa.accept(diff, temp)) { /* 採用 */ } // } // // // 受理ライン（スコア計算を途中打ち切りするとき） // double temp = sa.temperature(); // ll line = sa.threshold(temp); // 先に受理ラインを確定させる // ll new_score = 0; // for (int i = 0; i < N; i++) { // new_score += calc_partial(i); // if (new_score - cur_score > line) break; // 越えると確定したら打ち切る // } // if (new_score - cur_score <= line) { /* 採用 */ } template struct SA { double start_temp, end_temp, end_time; SA(double start_temp, double end_temp, double end_time) : start_temp(start_temp), end_temp(end_temp), end_time(end_time), t_begin(timer.elapsed()) { for (int i = 0; i < TABLE_SIZE; i++) { minus_log_table[i] = -log((i + 0.5) / TABLE_SIZE); temp_table[i] = start_temp * pow(end_temp / start_temp, (i + 0.5) / TABLE_SIZE); } } double temperature() const { return temp_table[min(TABLE_SIZE - 1, (int)(ratio() * TABLE_SIZE))]; } double temperature_linear() const { return start_temp + (end_temp - start_temp) * ratio(); } T threshold(double temp) const { return static_cast(temp * minus_log_table[rng.random32(TABLE_SIZE)]); } bool accept(T diff, double temp) const { if (diff <= 0) return true; return diff <= threshold(temp); } private: static constexpr int TABLE_SIZE = 1 << 12; double minus_log_table[TABLE_SIZE]; double temp_table[TABLE_SIZE]; double t_begin; double ratio() const { double dur = end_time - t_begin; if (dur <= 0) return 1.0; return min(1.0, (timer.elapsed() - t_begin) / dur); } }; // open addressing, linear probing。unordered_map より高速。 // Key にはハッシュ適用済みの値を渡す。 // // Usage: // HashMap seen(beam_width * 16); // n は格納要素数の 16 倍程度 // // auto [exists, idx] = seen.get_index(hash); // {存在するか, slot}。set/get には slot を渡す // seen.set(idx, hash, node_id); // slot に (key, value) を書く // int v = seen.get(idx); // slot の値を返す // seen.clear(); // 中身を捨てる。O(1) // // // 基本パターン（ビームサーチの重複除去） // auto [exists, idx] = seen.get_index(hash); // if (!exists) seen.set(idx, hash, node_id); // seen.clear(); // 次ターンへ template struct HashMap { explicit HashMap(uint32_t n) { if (n % 2 == 0) ++n; n_ = n; stamp_.assign(n_, 0); data_.resize(n_); } pair get_index(Key key) const { uint32_t i = (uint32_t)(key % n_); uint32_t start = i; while (stamp_[i] == current_stamp_) { if (data_[i].first == key) return {true, (int)i}; if (++i == n_) i = 0; if (i == start) return {false, (int)i}; } return {false, (int)i}; } void set(int i, Key key, T value) { stamp_[i] = current_stamp_; data_[i] = {key, value}; } T get(int i) const { return data_[i].second; } void clear() { if (++current_stamp_ == 0) { fill(stamp_.begin(), stamp_.end(), 0); current_stamp_ = 1; } } private: uint32_t n_; uint32_t current_stamp_ = 1; vector stamp_; vector> data_; }; // 整数集合 [0, n) に対する insert / erase / next / prev が O(log n / log 64) の 64 分木。 // std::set より高速。 // // Usage: // FastSet fs(N); // 宇宙 [0, N) の空集合を作る // // fs.insert(i); // i を追加する // fs.erase(i); // i を削除する // bool b = fs.contains(i); // i が含まれるか。O(1) // bool e = fs.empty(); // 空なら true // int x = fs.next(i); // i 以上の最小値。なければ N // int y = fs.prev(i); // i 以下の最大値。なければ -1 // int mn = fs.min_val(); // 最小値。空なら N // int mx = fs.max_val(); // 最大値。空なら -1 // // // 基本パターン（残っている要素を昇順に舐める） // for (int i = fs.min_val(); i < N; i = fs.next(i + 1)) { ... } struct FastSet { FastSet() : n_(0), log_(0) {} explicit FastSet(int n) : n_(n), log_(0) { if (n == 0) return; int m = n; do { d_.push_back(vector((m + B - 1) / B, 0)); m = (m + B - 1) / B; } while (m > 1); log_ = (int)d_.size(); } void insert(int i) { for (int h = 0; h < log_; h++) { d_[h][i / B] |= 1ULL << (i % B); i /= B; } } void erase(int i) { for (int h = 0; h < log_; h++) { d_[h][i / B] &= ~(1ULL << (i % B)); if (d_[h][i / B]) break; i /= B; } } bool contains(int i) const { if (log_ == 0) return false; return (d_[0][i / B] >> (i % B)) & 1; } bool empty() const { return log_ == 0 || d_[log_ - 1][0] == 0; } int next(int i) const { for (int h = 0; h < log_; h++) { int b = i / B; if (b >= (int)d_[h].size()) break; uint64_t f = d_[h][b] >> (i % B); if (!f) { i = b + 1; continue; } i += __builtin_ctzll(f); for (int g = h - 1; g >= 0; g--) i = i * B + __builtin_ctzll(d_[g][i]); return i; } return n_; } int prev(int i) const { for (int h = 0; h < log_; h++) { if (i < 0) break; int b = i / B; uint64_t f = d_[h][b] << (B - 1 - i % B); if (!f) { i = b - 1; continue; } i -= __builtin_clzll(f); for (int g = h - 1; g >= 0; g--) i = i * B + 63 - __builtin_clzll(d_[g][i]); return i; } return -1; } int min_val() const { return next(0); } int max_val() const { return prev(n_ - 1); } private: static constexpr int B = 64; int n_, log_; vector> d_; }; // 3x3 局所連結性。あるマスを消したとき、周囲の物体が分裂するかを判定する。 // // 見ているもの: // 中心 C は見ない。周囲 8 マスだけを「物体 / 空」に分け、C を除いたあとの // 連結成分数が 2 以上なら分裂（消せない）。0 または 1 ならつながったまま（消せる）。 // // 0 1 2 // 3 C 4 // 5 6 7 // // 引数: // grid : 2次元配列。grid[row][col] が真なら物体、偽なら空。 // 0/1 の int、bool など、if (grid[r][c]) が使える型なら何でもよい。 // 盤のサイズは grid.size() と grid[0].size() から取る。 // r, c : 消したいマス（0-index）。このマス自身の値は使わない。 // // conn8=true : 斜めもつながる（8連結） // conn8=false : 上下左右だけ（4連結） // // Usage: // ConnTable<> conn_table; // 8連結（グローバルに1つ用意してある） // ConnTable conn4; // 4連結 // // bool ok = conn_table.can_remove(grid, r, c); // (r,c) を消しても分裂しないなら true // // // 基本パターン // if (conn_table.can_remove(grid, r, c)) grid[r][c] = 0; template struct ConnTable { ConnTable() { for (int mask = 0; mask < 256; mask++) table[mask] = count_components(mask); } template bool can_remove(const Grid& grid, int r, int c) const { int H = (int)grid.size(); int W = H ? (int)grid[0].size() : 0; return table[neighbors(grid, r, c, H, W)] <= 1; } private: uint8_t table[256]; template uint8_t neighbors(const Grid& grid, int r, int c, int H, int W) const { static const int dr[] = {-1,-1,-1, 0, 0, 1, 1, 1}; static const int dc[] = {-1, 0, 1,-1, 1,-1, 0, 1}; uint8_t mask = 0; for (int k = 0; k < 8; k++) { int nr = r + dr[k], nc = c + dc[k]; if (nr >= 0 && nr < H && nc >= 0 && nc < W && grid[nr][nc]) mask |= 1 << k; } return mask; } static int count_components(int mask) { static const int adj8[8][4] = { {1, 3, -1, -1}, {0, 2, 3, 4}, {1, 4, -1, -1}, {0, 1, 5, 6}, {1, 2, 6, 7}, {3, 6, -1, -1}, {3, 4, 5, 7}, {4, 6, -1, -1}, }; static const int adj4[8][4] = { {1, 3, -1, -1}, {0, 2, -1, -1}, {1, 4, -1, -1}, {0, 5, -1, -1}, {2, 7, -1, -1}, {3, 6, -1, -1}, {5, 7, -1, -1}, {4, 6, -1, -1}, }; const auto& adj = conn8 ? adj8 : adj4; int comp = 0; uint8_t visited = 0; for (int i = 0; i < 8; i++) { if (!((mask >> i) & 1) || (visited >> i) & 1) continue; comp++; uint8_t stk = 1 << i; visited |= 1 << i; while (stk) { int u = __builtin_ctz(stk); stk &= stk - 1; for (int k = 0; k < 4 && adj[u][k] != -1; k++) { int v = adj[u][k]; if (((mask >> v) & 1) && !((visited >> v) & 1)) { visited |= 1 << v; stk |= 1 << v; } } } } return comp; } }; ConnTable<> conn_table; // 8連結。4連結が必要なら ConnTable を別途宣言する。 // 離散ベイズ推定器。状態 0..n-1 の事後分布を log 空間で管理する。 // likelihood[i] = P(obs | state=i) の計算は問題依存（ノイズモデルから導く）。 // // Usage: // BayesEstimator be(N); // 一様事前分布 // BayesEstimator be(prior); // カスタム事前分布 prior[i] = P(state=i) // be.update(likelihood); // likelihood[i] = P(obs | state=i) // be.update_log(log_likelihood); // log 尤度を直接渡す版 // double p = be.prob(i); // P(state=i | 全観測) // int s = be.argmax(); // 最大事後確率の状態 // vector ps = be.probs(); // 全確率を vector で返す // // 典型的な log 尤度（update_log に渡す）: // // ガウスノイズ // for (int i = 0; i < N; i++) log_lik[i] = -(obs-expected[i])*(obs-expected[i]) / (2*sigma*sigma); // // 二値ノイズ（正解率 p） // for (int i = 0; i < N; i++) log_lik[i] = log(obs == true_val[i] ? p : 1.0-p); struct BayesEstimator { explicit BayesEstimator(int n) : n(n), log_prob(n, -log((double)n)) {} explicit BayesEstimator(vector prior) : n((int)prior.size()), log_prob(prior.size()) { for (int i = 0; i < n; i++) log_prob[i] = log(prior[i]); normalize(); } void update(const vector& likelihood) { for (int i = 0; i < n; i++) log_prob[i] += log(likelihood[i]); normalize(); } void update_log(const vector& log_likelihood) { for (int i = 0; i < n; i++) log_prob[i] += log_likelihood[i]; normalize(); } double prob(int i) const { return exp(log_prob[i]); } int argmax() const { return int(max_element(log_prob.begin(), log_prob.end()) - log_prob.begin()); } vector probs() const { vector p(n); for (int i = 0; i < n; i++) p[i] = prob(i); return p; } private: int n; vector log_prob; void normalize() { double mx = *max_element(log_prob.begin(), log_prob.end()); double s = 0; for (int i = 0; i < n; i++) s += exp(log_prob[i] - mx); double log_s = mx + log(s); for (int i = 0; i < n; i++) log_prob[i] -= log_s; } }; // Dial's アルゴリズム（バケットキュー）。辺コストが小さい整数のとき priority_queue より高速。 // max_cost = 最大辺コスト（BFS なら 1） // max_dist = 探索する最大距離（省略時は全到達頂点を探索） // 未到達は INT_MAX。 // // Usage: // vector>> adj(N); // adj[v] = {{隣接, 重み}, ...} // auto dist = dial(start, N, adj, 1); // BFS // auto dist = dial(start, N, adj, max_cost); // 全頂点 // auto dist = dial(start, N, adj, max_cost, max_dist); // 距離 max_dist 以内 vector dial(int start, int n, const vector>>& adj, int max_cost, int max_dist = -1) { const int D = max_cost + 1; vector dist(n, INT_MAX); vector> bucket(D); dist[start] = 0; bucket[0].push_back(start); int pending = 1; for (int d = 0; pending > 0; d++) { int bi = d % D; for (size_t k = 0; k < bucket[bi].size(); k++) { int v = bucket[bi][k]; if (dist[v] != d) continue; for (auto [u, w] : adj[v]) { if (dist[v] + w < dist[u]) { dist[u] = dist[v] + w; if (max_dist < 0 || dist[u] <= max_dist) { bucket[dist[u] % D].push_back(u); pending++; } } } } pending -= (int)bucket[bi].size(); bucket[bi].clear(); } return dist; } struct Solver { Solver() { timer.reset(); } void read() {} void solve() {} void print() const {} }; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); Solver solver; solver.read(); solver.solve(); solver.print(); return 0; }