好用的模板
网络流合集。包含 ISAP 最大流，Dinic + Dijkstra 费用流
//template <typename T>
//using heap = std::priority_queue<T, std::vector<T>, std::greater<T>>;
class network_flow_t { // 记得边是从 0 起的！！！
std::vector<std::vector<int>> head; // 存图的顶点连哪些边（存索引）
std::vector<std::pair<int, int>> edges{}; // 所有的边
std::vector<int> depth, current, costs, distance, h; // current 用于当前弧优化， h 是势
std::vector<bool> visited; // 用于 dinic 算法的 dfs
std::unordered_map<int, int> gap{}; // isap 的 gap 优化
static const int INF = INT32_MAX;
public:
// 只给定顶点数，边数实时动态分配（数据过大可能会引发 std::bac_alloc）
network_flow_t(size_t len) : head(len), depth(len) {}
// 给定顶点数和边数（会自动计算反向边），适用边数确定的情况
network_flow_t(size_t len, size_t cnt, bool use_cost = false)
: head(len), depth(len) {
edges.reserve(cnt << 1); // 考虑反向边，要乘 2
if (use_cost) // 启用费用边模式时还要分配它的空间
costs.reserve(cnt << 1);
}
// FROM u, TO v, Flow f
void connect(int u, int v, int f) {
head[u].emplace_back(edges.size());
edges.emplace_back(v, f);
head[v].emplace_back(edges.size()); // 建立反向边，这样建边，可以直接通过异或求得反向边的编号
edges.emplace_back(u, 0);
}
// From u, To v, Flow f, Cost c
void connect(int u, int v, int f, int c) {
connect(u, v, f);
costs.emplace_back(c);
costs.emplace_back(-c); // 反向边的费用是负数
}
// 以下为最大流算法 isap 实现
private:
void _isap_bfs(int end) { // 从后往前分层
std::fill(depth.begin(), depth.end(), -1);
gap.clear();
depth[end] = 0;
gap[end] = 1;
std::queue<int> queue;
queue.emplace(end);
do {
auto u = queue.front();
queue.pop();
for (const auto &idx : head[u]) {
const auto &[v, f] = edges[idx];
if (depth[v] != -1)
continue;
depth[v] = depth[u] + 1;
gap[depth[v]]++;
queue.emplace(v);
}
} while (not queue.empty());
}
int _isap_dfs(int u, int flow, const int &start, const int &end) {
if (u == end)
return flow;
int used = 0;
for (int &cur = current[u]; cur < head[u].size(); ++cur) {
const auto &idx = head[u][cur];
auto &&[v, f] = edges[idx];
if (f < 1 or depth[u] != depth[v] + 1) // depth 是反向的，记住
continue;
auto spend = _isap_dfs(v, std::min(f, flow - used), start, end);
if (spend == 0)
continue;
auto &&[_, rf] = edges[idx ^ 1]; // 求出这条边的反向边
f -= spend;
rf += spend;
used += spend;
if (used == flow)
return flow;
}
--gap[depth[u]];
if (gap[depth[u]] == 0)
depth[start] = head.size() + 1;
++depth[u];
++gap[depth[u]];
return used;
}
public:
long maximum_flow(int start, int end) {
long result = 0;
_isap_bfs(end);
current.resize(head.size());
while (depth[start] < head.size()) {
std::fill(current.begin(), current.end(), 0);
result += _isap_dfs(start, INF, start, end);
}
return result;
}
// 以下为最小费用最大流算法 dinic + dijkstra 实现
private:
bool _dijkstra(int start, int end) {
std::fill(distance.begin(), distance.end(), INF);
std::heap<std::pair<long, int>> heap;
distance[start] = 0;
heap.emplace(distance[start], start);
do {
auto [d, u] = heap.top();
heap.pop();
if (distance[u] < d)
continue;
for (const auto &idx : head[u]) {
const auto &[v, f] = edges[idx];
const auto &c = costs[idx];
const auto new_distance = distance[u] + c + h[u] - h[v];
if (f == 0 or distance[v] <= new_distance)
continue;
distance[v] = new_distance;
heap.emplace(distance[v], v);
}
} while (not heap.empty());
return distance[end] != INF;
}
int _dinic_dfs(int u, int flow, const int &start, const int &end) {
if (u == end)
return flow;
int used = 0;
visited[u] = true;
for (int &cur = current[u]; cur < head[u].size(); ++cur) {
const auto &idx = head[u][cur];
auto &&[v, f] = edges[idx];
const auto &c = costs[idx];
const auto new_distance = distance[u] + c + h[u] - h[v];
if (visited[v] or f == 0 or distance[v] != new_distance)
continue;
auto spend = _dinic_dfs(v, std::min(flow - used, f), start, end);
auto &&[_, rf] = edges[idx ^ 1];
f -= spend;
rf += spend;
used += spend;
if (flow == used)
break;
}
visited[u] = false;
return used;
}
public:
std::pair<long, long> minimum_cost_maximum_flow(int start, int end) {
long flow = 0, cost = 0;
h.assign(head.size(), 0);
distance.resize(head.size());
visited.assign(head.size(), false);
current.resize(head.size());
while (_dijkstra(start, end)) {
std::fill(current.begin(), current.end(), 0);
auto result = _dinic_dfs(start, INF, start, end);
for (int i = 0; i < head.size(); ++i)
h[i] += distance[i] == INF ? 0 : distance[i];
flow += result;
cost += result * h[end];
}
return {cost, flow};
}
public:
void clear_edges() {
head.assign(head.size(), std::vector<int>());
edges.clear();
costs.clear();
gap.clear();
}
}; // 记得边是从 0 起的！！！欧拉筛
class prime_table {
std::vector<long> primes;
std::vector<bool> isPrimes;
public:
prime_table(const long &n) : isPrimes(n + 1, true) {
for (long i = 2; i <= n; ++i) {
if (isPrimes[i])
primes.emplace_back(i);
for (auto &&prime : primes) {
if (i * prime > n)
break;
isPrimes[i * prime] = false;
if (i % prime == 0)
break;
}
}
}
std::vector<long> get_primes() {
return primes;
}
bool is_primes(const size_t &index) {
return isPrimes[index];
}
long operator[](const size_t &index) {
return primes[index];
}
};
珂树
template<typename T>
class ChthollyTree {
set<tuple<size_t, size_t, T> > tree;
using iterator = set<tuple<size_t, size_t, T> >::iterator;
iterator split(const size_t &posation) {
auto it = tree.lower_bound({posation, 0, 0});
if(it != tree.end() and get<0>(*it) == posation)
return it;
--it;
auto [left, right, data] = *it;
tree.erase(it);
if (left < posation)
tree.emplace(left, posation - 1, data);
if (right >= posation)
return tree.emplace(posation, right, data).first;
return tree.end();
}
public:
// 左闭右开
void assign(const size_t &left, const size_t &right, const T & data) {
auto end = split(right), begin = split(left);
tree.erase(begin, end);
tree.emplace(left, right - 1, data);
}
void add_node(const tuple<size_t, size_t, T>& node) {
tree.emplace(node);
}
// 左闭右开
void add_range(const size_t &left, const size_t &right, const T & data) {
auto end = split(right), begin = split(left);
for(auto it = begin; it != end; ++it)
get<2>(*it) += data;
}
// 左闭右开
T range_sum(const size_t &left, const size_t &right) {
auto end = split(right), begin = split(left);
T result = 0;
for(auto it = begin; it != end; ++it)
result += get<2>(*it);
return result;
}
T range_sum(const size_t &left, const size_t &right, const T &mod) {
auto end = split(right), begin = split(left);
T result = 0;
for(auto it = begin; it != end; ++it)
result = (result + get<2>(*it)) % mod;
return result;
}
// 左闭右开
T kth_element(const size_t &left, const size_t &right, const size_t k) {
auto end = split(right), begin = split(left);
list<pair<T, size_t>> nodes;
for(auto it = begin; it != end; ++it) {
auto &&[left, right, data] = *it;
nodes.emplace_back(data, right - left + 1);
}
for(auto &&[data, span] : nodes) {
k -= span;
if (k <= 0)
return data;
}
return -1;
}
T ask(const size_t &posation) {
return get<2>(prev(tree.upper_bound({posation, -1, T{}})));
}
T ask_range(const size_t &left, const size_t &right) {
auto end = split(right), begin = split(left);
T result{};
for(auto it = begin; it != end; ++it)
result += get<2>(*it);
return result;
}
ChthollyTree(const vector<T> &array) {
const auto len = array.size();
for (std::int64_t l = 0, r = 0; r < len; l = r) {
while (r < len and array[l] == array[r])
r++;
add_node({l + 1, r, array[l]});
}
}
void show() {
for(auto &&[left, right, data] : tree) {
for(auto i = left; i <= right; ++i)
cout << data << endl;
}
}
};跳表
#include <iostream>
#include <limits>
#include <random>
#include <stdexcept>
#include <string>
#include <vector>
template <typename T, size_t kMaxLevel = 16> class Skiplist {
struct Node {
T Key;
std::vector<size_t> SkipSpans;
std::vector<Node *> Nexts;
Node(const T &key, const size_t &size)
: Key(key), SkipSpans(size + 1, 0), Nexts(size + 1, nullptr) {}
};
std::bernoulli_distribution rand_;
std::minstd_rand seed_{std::random_device{}()};
size_t count_ = 0;
Node *head_ = new Node(std::numeric_limits<T>::min(), kMaxLevel);
size_t random_level() {
size_t level = 1;
while (level < kMaxLevel and rand_(seed_))
level++;
return level;
}
std::pair<std::vector<Node *>, std::vector<size_t>>
search_updates(const T &item) {
std::vector<Node *> updates(kMaxLevel + 1);
auto current = head_;
std::vector<size_t> totalSpans(kMaxLevel + 2, 0);
for (auto level = kMaxLevel; level != -1; --level) {
totalSpans[level] = totalSpans[level + 1];
while (current->Nexts[level] and
current->Nexts[level]->Key < item) {
totalSpans[level] += current->SkipSpans[level];
current = current->Nexts[level];
}
updates[level] = current;
}
return {updates, totalSpans};
}
Node *lower_bound(const T &item) {
auto current = head_;
for (auto level = kMaxLevel; level != -1; --level)
while (current->Nexts[level] and current->Nexts[level]->Key < item)
current = current->Nexts[level];
return current;
}
Node *upper_bound(const T &item) {
auto current = head_;
for (auto level = kMaxLevel; level != -1; --level)
while (current->Nexts[level] and current->Nexts[level]->Key <= item)
current = current->Nexts[level];
return current;
}
public:
bool empty() { return count_ == 0; }
size_t size() { return count_; }
void add(const T &item) {
auto [updates, totalSpans] = search_updates(item);
auto level = random_level();
auto newNode = new Node(item, level);
if (newNode == nullptr)
throw std::bad_alloc();
const auto totalSpan = totalSpans.front() + 1;
for (size_t currentLevel = 0; currentLevel <= level; ++currentLevel) {
newNode->Nexts[currentLevel] =
updates[currentLevel]->Nexts[currentLevel];
updates[currentLevel]->Nexts[currentLevel] = newNode;
auto diff = totalSpan - totalSpans[currentLevel];
if (newNode->Nexts[currentLevel])
newNode->SkipSpans[currentLevel] =
updates[currentLevel]->SkipSpans[currentLevel] - diff + 1;
updates[currentLevel]->SkipSpans[currentLevel] = diff;
}
// 记得处理在高层前插入低层的情况的 skipSpan
for (auto currentLevel = level + 1; currentLevel <= kMaxLevel;
++currentLevel)
if (updates[currentLevel]->Nexts[currentLevel])
updates[currentLevel]->SkipSpans[currentLevel]++;
count_++;
}
bool erase(const T &item) {
if (empty())
return false;
auto updates = search_updates(item).first;
auto node = updates.front()->Nexts.front();
if (node == nullptr or node->Key != item)
return false;
for (size_t currentLevel = 0; currentLevel < node->Nexts.size();
++currentLevel) {
if (updates[currentLevel]->Nexts[currentLevel] != node)
continue;
updates[currentLevel]->Nexts[currentLevel] =
node->Nexts[currentLevel];
if (updates[currentLevel]->Nexts[currentLevel])
updates[currentLevel]->SkipSpans[currentLevel] +=
node->SkipSpans[currentLevel] - 1;
else
updates[currentLevel]->SkipSpans[currentLevel] = 0;
}
// 记得处理在高层前删除低层的情况的 skipSpan
for (auto currentLevel = node->Nexts.size(); currentLevel <= kMaxLevel;
++currentLevel)
if (updates[currentLevel]->Nexts[currentLevel])
updates[currentLevel]->SkipSpans[currentLevel]--;
delete node;
count_--;
return true;
}
bool search(const T &item) {
auto updates = search_updates(item).first;
auto node = updates.front()->Nexts.front();
return node and node->Key == item;
}
size_t rank_of(const T &item) {
return search_updates(item).second.front() + 1;
}
T nth_element(const size_t &rank) {
if (rank > count_)
throw std::out_of_range("rank can't not greater than list size");
size_t currentRank = 0;
auto current = head_;
for (auto currentLevel = kMaxLevel; currentLevel != -1; --currentLevel)
while (current->Nexts[currentLevel] and
current->SkipSpans[currentLevel] + currentRank <= rank) {
currentRank += current->SkipSpans[currentLevel];
current = current->Nexts[currentLevel];
}
return current->Key;
}
T lower_to(const T &item) { return lower_bound(item)->Key; }
T upper_to(const T &item) { return upper_bound(item)->Nexts[0]->Key; }
class iterator {
Node *current_;
public:
iterator(Node *start) : current_(start) {}
T &operator*() { return current_->Key; }
iterator &operator++() {
current_ = current_->Nexts[0];
return *this;
}
bool operator!=(const iterator &other) const {
return current_ != other.current_;
}
};
iterator begin() const { return iterator(head_->Nexts[0]); }
iterator end() const { return iterator(nullptr); }
void makeView() {
std::endl(std::cout);
for (auto current = head_; current != nullptr;
current = current->Nexts[0]) {
for (size_t i = 0; i < current->Nexts.size(); ++i)
std::cout << current->Key << '['
<< (current->Nexts[i]
? std::to_string(current->Nexts[i]->Key)
: "nullptr")
<< "](" << current->SkipSpans[i] << ") ";
std::endl(std::cout);
}
std::endl(std::cout);
}
Skiplist(const double &p = 0.5) : rand_(p) {}
~Skiplist() {
auto current = head_;
while (current) {
auto next = current->Nexts[0];
delete current;
current = next;
}
}
};组合数
class combination {
vector<int64_t> inv_factorial_, factorial_;
int64_t mod_;
static int64_t quick_power(int64_t base, int64_t power, int64_t mod) {
auto result = 1;
while (power) {
if (power & 1)
result = (result * base) % mod;
base = (base * base) % mod;
power >>= 1;
}
return result;
}
public:
combination(const int64_t &n, const int64_t &mod)
: inv_factorial_(n + 1), factorial_(n + 1), mod_(mod) {
factorial_[0] = 1;
for (auto &&i = 1ll; i <= n; ++i)
factorial_[i] = factorial_[i - 1] * i % mod_;
inv_factorial_[n] = quick_power(factorial_[n], mod_ - 2, mod_);
for(auto i = n - 1; i >= 0; --i)
inv_factorial_[i] = inv_factorial_[i + 1] * (i + 1) % mod_;
}
int64_t C(const int64_t &down, const int64_t &up) const {
if(up > down or up < 0)
return 0;
return factorial_[down] * inv_factorial_[up] % mod_ * inv_factorial_[down - up] % mod_;
}
};
auto loader = combination(2e6, 998244353);究极压位高精度整数
#include <bits/stdc++.h>
#pragma region heads
#ifndef _MSC_VER
#if __cplusplus >= 202000
template <typename... Args>
void print(const std::string_view fmt, const Args &...args) {
std::cout << std::vformat(fmt, std::make_format_args(args...));
}
template <typename... Args>
void println(const std::string_view fmt, const Args &...args) {
std::cout << std::vformat(fmt, std::make_format_args(args...));
std::cout.put('\n');
}
void print(const std::string_view s) { std::cout << s; }
void println(const std::string_view s) { std::cout << s << '\n'; }
#endif
#endif
void println() { std::cout.put('\n'); }
#pragma region Bigint
class Bigint {
using int128_t = __int128;
std::vector<uint64_t> _data;
constexpr static uint64_t _base = 10000000000000000000ull; // 1e19
constexpr static uint8_t _len = 19;
bool _isNegative;
Bigint(const std::vector<uint64_t> &data, const bool isNegative)
: _data(data), _isNegative(isNegative) {
}
// 快速幂
static Bigint pow(Bigint &base, Bigint &power) {
Bigint result = 1;
while (power) {
if (power.is_odd())
result *= base;
base *= base;
power /= 2;
}
return result;
}
static void lhsToValue(const Bigint &value, Bigint &other) {
std::string s = other.to_string();
for (int128_t i = value.to_string().size() - s.size(); i--;)
s += '0';
other = Bigint(s);
}
static void rhs(Bigint &other) {
for (int128_t i = other._data.size() - 1, mod = 0; i >= 0; --i) {
const auto tmp = mod * _base + other._data[i];
mod = tmp % 10;
other._data[i] = tmp / 10;
if (other._data[i] == 0 and i and i + 1 == other._data.size())
other._data.pop_back();
}
}
Bigint div_mod(const Bigint &other, Bigint &modulo) const {
if (other == 0)
throw std::invalid_argument("Division by zero");
if (*this == 0) {
modulo = 0;
return 0;
}
const bool resultNegative = _isNegative != other._isNegative;
const bool moduloNegative = _isNegative;
Bigint current(_data, false), dividend(other._data, false);
if (current < dividend) {
modulo = *this;
return 0;
}
const auto raw_dividend = dividend;
// 对齐位数
lhsToValue(current, dividend);
std::string s;
for (size_t total = 0; current >= raw_dividend;) {
while (current >= dividend) {
current -= dividend;
total++;
}
if (total or not s.empty()) {
s += std::to_string(total);
total = 0;
}
rhs(dividend);
}
modulo = Bigint(current._data, moduloNegative);
if (resultNegative)
s = "-" + s;
while (dividend >= raw_dividend) {
rhs(dividend);
s += '0';
}
return Bigint(s);
}
public:
// 隐式类型转换
explicit operator bool() const { return *this != Bigint(0); }
explicit operator int64_t() const { return std::stoll(to_string()); }
explicit operator int() const { return std::stoi(to_string()); }
Bigint() : _data(1), _isNegative(false) {
}
// ReSharper disable once CppNonExplicitConvertingConstructor
Bigint(const int64_t &value) : _data(1) {
// NOLINT(*-explicit-constructor)
_isNegative = value < 0;
_data.front() = _isNegative ? -value : value;
}
Bigint(const Bigint &other) {
_data = other._data;
_isNegative = other._isNegative;
}
// ReSharper disable once CppNonExplicitConvertingConstructor
Bigint(const std::string &value) {
// NOLINT(*-explicit-constructor)
_isNegative = value.front() == '-';
int128_t r = value.size(), l = r - _len;
for (uint64_t val; l >= _isNegative; l -= _len, r -= _len) {
#if __cplusplus < 201700L
val = 0;
for (int128_t i = l; i < r; ++i)
val = val * 10 + value[i] - '0';
#else
std::from_chars(value.data() + l, value.data() + r, val);
#endif
_data.emplace_back(val);
}
#if __cplusplus < 201700L
if (r > _isNegative) {
uint64_t val = 0;
#else
if (uint64_t val; r > _isNegative) {
#endif
#if __cplusplus < 201700L
for (int128_t i = _isNegative; i < r; ++i)
val = val * 10 + value[i] - '0';
#else
std::from_chars(value.data() + _isNegative, value.data() + r, val);
#endif
_data.emplace_back(val);
}
}
friend std::istream &operator>>(std::istream &is, Bigint &other) {
std::string s;
is >> s;
other = Bigint(s);
return is;
}
[[nodiscard]] std::string to_string() const {
std::ostringstream ss;
if (_isNegative)
ss.put('-');
bool isTrimming = true;
for (size_t i = _data.size() - 1; i > 0; --i) {
if (_data[i] == 0 and isTrimming)
continue;
if (isTrimming) {
isTrimming = false;
ss << _data[i];
continue;
}
ss << std::setfill('0') << std::setw(_len) << _data[i];
}
if (not isTrimming)
ss << std::setfill('0') << std::setw(_len);
ss << _data.front();
return ss.str();
}
friend std::ostream &operator<<(std::ostream &os, const Bigint &value) {
os << value.to_string();
return os;
}
private:
template<typename T>
static int compare(const T &left, const T &right) {
if (left > right)
return 1;
if (left < right)
return -1;
return 0;
}
int compare(const Bigint &other) const {
const auto &NegativeCheck = [](const int &cmp, const bool &isNegative) {
if (isNegative) // 符号相同，负数越长越小，正数越长越大
return cmp == 1 ? -1 : 1;
return cmp;
};
if (_isNegative != other._isNegative) // 不同号的情况下，负数明显更小
return _isNegative ? -1 : 1;
auto cmp = compare(_data.size(), other._data.size());
if (cmp != 0)
return NegativeCheck(cmp, _isNegative);
for (int128_t i = _data.size() - 1; i >= 0; --i) {
cmp = compare(_data[i], other._data[i]);
if (cmp == 0)
continue;
return NegativeCheck(cmp, _isNegative);
}
return 0;
}
public:
#if __cplusplus >= 202000L
std::strong_ordering operator<=>(const Bigint &other) const {
switch (compare(other)) {
case 1: return std::strong_ordering::greater;
case 0: return std::strong_ordering::equal;
default: return std::strong_ordering::less;
}
}
bool operator==(const Bigint &other) const = default;
#else
bool operator <(const Bigint &other) const {
return compare(other) < 0;
}
bool operator <=(const Bigint &other) const {
return compare(other) <= 0;
}
bool operator >(const Bigint &other) const {
return compare(other) > 0;
}
bool operator >=(const Bigint &other) const {
return compare(other) >= 0;
}
bool operator==(const Bigint &other) const {
return _isNegative == other._isNegative and _data == other._data;
}
bool operator !=(const Bigint &other) const {
return not this->operator==(other);
}
#endif
// 取负数
Bigint operator-() const { return Bigint(_data, not _isNegative); }
bool is_odd() const { return _data.front() & 1; }
bool is_even() const { return not is_odd(); }
Bigint operator+(const Bigint &other) const {
if (_isNegative != other._isNegative)
return _isNegative
? Bigint(other) - Bigint(_data, false)
: operator-(Bigint(other._data, false));
int128_t carry = 0;
const auto max_size = std::max(_data.size(), other._data.size());
auto backup = *this;
Bigint result = other;
backup._data.resize(max_size, 0);
result._data.resize(max_size, 0);
for (int i = 0; i < max_size; ++i) {
const auto tmp = carry + backup._data[i] + result._data[i];
result._data[i] = tmp % _base;
carry = (tmp - result._data[i]) / _base;
}
return result;
}
Bigint operator+=(const Bigint &other) { return *this = *this + other; }
Bigint operator*(const Bigint &other) const {
if (this->to_string() == "0" or other.to_string() == "0")
return 0;
Bigint result(std::vector<uint64_t>(0), false);
int128_t carry = 0;
for (size_t i = 0; i < _data.size(); i++) {
Bigint each_data(std::vector<uint64_t>(i), false);
for (const auto &j: other._data) {
const auto tmp = static_cast<int128_t>(_data[i]) * j + carry;
each_data._data.emplace_back(tmp % _base);
carry = tmp / _base;
}
if (carry != 0) {
each_data._data.emplace_back(carry % _base);
carry = 0;
}
result += each_data;
}
return Bigint(result._data, _isNegative != other._isNegative);
}
Bigint operator*=(const Bigint &other) { return *this = *this * other; }
Bigint operator-(const Bigint &other) const {
if (_isNegative != other._isNegative)
return *this + Bigint(other._data, _isNegative);
if (_isNegative) // (-a) - (-b) => (-a) + b => b - a
return Bigint(other._data, false) - Bigint(_data, false);
const bool isNegative = *this < other; // 小减大，必然是负号，反之不是
const auto &bigSide = isNegative ? other : *this;
const auto &smallSide = isNegative ? *this : other;
Bigint result(std::vector<uint64_t>(0), isNegative);
int128_t carry = 0;
for (size_t i = 0; i < smallSide._data.size(); ++i) {
auto tmp = carry + bigSide._data[i] - smallSide._data[i];
carry = 0;
if (tmp < 0) {
carry = -1;
tmp += _base;
}
result._data.emplace_back(tmp);
}
for (size_t i = result._data.size(); i < bigSide._data.size(); ++i) {
const auto tmp = carry + bigSide._data[i];
carry = 0;
result._data.emplace_back(tmp);
}
if (carry != 0) // 借多的要还回去
result._data.back() -= carry;
while (result._data.size() > 1 and result._data.back() == 0)
result._data.pop_back();
return result;
}
Bigint operator-=(const Bigint &other) { return *this = *this - other; }
Bigint operator/(const Bigint &other) const {
Bigint modulo;
return div_mod(other, modulo);
}
Bigint operator/=(const Bigint &other) { return *this = *this / other; }
Bigint operator%(const Bigint &other) const {
Bigint modulo;
div_mod(other, modulo);
return modulo;
}
Bigint operator%=(const Bigint &other) { return *this = *this % other; }
Bigint operator<<(const Bigint &other) const {
Bigint base = 2, power = other;
return *this * pow(base, power);
}
Bigint operator<<=(const Bigint &other) { return *this = *this << other; }
Bigint operator>>(const Bigint &other) const {
Bigint base = 2, power = other;
return *this / pow(base, power);
}
Bigint operator>>=(const Bigint &other) { return *this = *this >> other; }
// 前自增
Bigint &operator++() {
*this += 1;
return *this;
}
// 后自增
Bigint operator++(int) {
auto temp = *this;
++*this;
return temp;
}
// 前自减
Bigint &operator--() {
*this -= 1;
return *this;
}
// 后自减
Bigint operator--(int) {
auto temp = *this;
--*this;
return temp;
}
};
#if __cplusplus >= 202000
// C++20 的 format 支持
template<>
struct std::formatter<Bigint> {
constexpr static auto parse(const std::format_parse_context &ctx) {
return ctx.begin();
}
static auto format(const Bigint &number, std::format_context &ctx) {
return std::format_to(ctx.out(), "{}", number.to_string());
}
};
#endif
using Int = Bigint;
#pragma endregion
#pragma endregion
using namespace std;
#define T_CASE 0
auto solve() -> void {
Int a, b;
cin >> a >> b;
println("{}", a + b);
println("{}", a - b);
println("{}", a * b);
println("{}", a / b);
println("{}", a % b);
}
auto main() -> signed {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int64_t t{1};
#if T_CASE
cin >> t;
#endif
while (t--)
solve();
return 0;
}字符串简单处理套件
#include <bits/stdc++.h>
class PalindromeHelper {
std::string string_;
size_t n;
std::vector<size_t> pow_, hash_, rhash_;
// [1, n] [l, r]
size_t get_hash(int l, int r) const {
assert(l <= r);
return hash_[r] - hash_[l - 1] * pow_[r - l + 1];
}
// [1, n] [l, r]
size_t get_rhash(int l, int r) const {
assert(l <= r);
return rhash_[n - l + 1] - rhash_[n - r] * pow_[r - l + 1];
}
public:
PalindromeHelper(std::string_view string, size_t prime = 233) : string_(string) {
n = string.length();
hash_.resize(n + 1);
rhash_.resize(n + 1);
pow_.resize(n + 1);
pow_[0] = 1;
hash_[0] = rhash_[0] = 0;
for (size_t i = 0; i < n; ++i) {
hash_[i + 1] = hash_[i] * prime + string[i];
rhash_[i + 1] = rhash_[i] * prime + string[n - i - 1];
pow_[i + 1] = pow_[i] * prime;
}
}
// 0-index
bool is_palindrome(int l, int r) const {
return get_hash(l + 1, r + 1) == get_rhash(l + 1, r + 1);
}
std::string_view longest_palindrome() {
if (string_.empty())
return "";
size_t max_length = 1, start = 0;
for (size_t r = 0, current = 0; r < n; ++r) {
for (auto length = std::min(current + 2, r + 1); length; --length) {
size_t l = r - length + 1;
if (not is_palindrome(l, r))
continue;
current = length;
break;
}
// 更新全局最长回文
if (current > max_length) {
max_length = current;
start = r - current + 1;
}
}
return std::string_view(string_.data() + start, max_length);
}
};
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
string s;
cin >> s;
PalindromeHelper helper(s);
cout << helper.longest_palindrome().length() << '\n';
}128位整形
#include <bits/stdc++.h>
using i128 [[maybe_unused]] = __int128;
const i128 &INT128_MAX = (i128(INT64_MAX) << 64) | UINT64_MAX;
const i128 &INT128_MIN = ~INT128_MAX;
i128 operator ""_i(const unsigned long long &value) {
return i128(value);
}
i128 operator ""_i(const char *str, std::size_t len) {
bool f = str[0] == '-';
if (not std::all_of(str + f, str + len, isdigit))
throw std::invalid_argument("无法转换为整数");
i128 value = 0;
for (int i = 0 + f; i < len; ++i)
value = (value << 3) + (value << 1) + (str[i] ^ '0');
return f ? -value : value;
}
std::istream &operator>>(std::istream &is, i128 &value) {
value = 0;
bool isNegative = false;
int c = is.get();
while (not isdigit(c)) {
if (c == '-')
isNegative = true;
c = is.get();
}
while (isdigit(c)) {
value = (value << 3) + (value << 1) + (c ^ '0');
c = is.get();
}
if (isNegative)
value = -value;
return is;
}
std::ostream &operator<<(std::ostream &os, i128 value) {
if (value == 0) {
os.put('0');
return os;
}
static char sta[40];
unsigned char top = 0;
if (value < 0) {
sta[top++] = static_cast<char>(-(value % 10));
value /= 10;
value = ~value + 1;
os.put('-');
}
for (; value; value /= 10)
sta[top++] = static_cast<char>(value % 10);
for (; top--;)
os.put(static_cast<char>(sta[top] ^ '0'));
return os;
}简单矩阵及其矩阵的运算
#include <bits/stdc++.h>
using namespace std;
template <typename T> class Matrix {
vector<vector<T>> mat;
size_t d;
public:
Matrix(size_t n) : mat(n, vector<T>(n, 0)) {
d = n;
for (size_t i = 0; i < n; ++i)
mat[i][i] = 1;
}
Matrix(const vector<vector<T>> &&val) : mat(val), d(val.size()) {}
Matrix(const vector<vector<T>> &val) : mat(val), d(val.size()) {}
Matrix operator+(const Matrix &other) {
Matrix res = other;
for (size_t i = 0; i < d; ++i)
for (size_t j = 0; j < d; ++j)
res.mat[i][j] = mat[i][j] + other.mat[i][j];
return res;
}
Matrix operator+=(const Matrix &other) {
for (size_t i = 0; i < d; ++i)
for (size_t j = 0; j < d; ++j)
mat[i][j] += other.mat[i][j];
return mat;
}
Matrix operator-(const Matrix &other) {
Matrix res = other;
for (size_t i = 0; i < d; ++i)
for (size_t j = 0; j < d; ++j)
res.mat[i][j] = mat[i][j] - other.mat[i][j];
return res;
}
Matrix operator-=(const Matrix &other) {
for (size_t i = 0; i < d; ++i)
for (size_t j = 0; j < d; ++j)
mat[i][j] -= other.mat[i][j];
return mat;
}
Matrix operator*(const Matrix &other) {
Matrix res = other;
for (size_t i = 0; i < d; ++i)
for (size_t j = 0; j < d; ++j) {
res.mat[i][j] = 0;
for (size_t k = 0; k < d; ++k)
res.mat[i][j] += mat[i][k] * other.mat[k][j];
}
return res;
}
Matrix operator*=(const Matrix &other) {
Matrix res = other;
for (size_t i = 0; i < d; ++i)
for (size_t j = 0; j < d; ++j) {
res.mat[i][j] = 0;
for (size_t k = 0; k < d; ++k)
res.mat[i][j] += mat[i][k] * other.mat[k][j];
}
mat = res.mat;
return res;
}
Matrix mul(const Matrix &other, const T mod) {
Matrix res = other;
for (size_t i = 0; i < d; ++i)
for (size_t j = 0; j < d; ++j) {
res.mat[i][j] = 0;
for (size_t k = 0; k < d; ++k)
res.mat[i][j] += mat[i][k] * other.mat[k][j] % mod;
res.mat[i][j] %= mod;
}
return res;
}
Matrix operator^(size_t power) {
Matrix res(d), base = *this;
while (power) {
if (power & 1)
res = res * base;
power >>= 1;
base = base * base;
}
return res;
}
Matrix pow(size_t power, const T mod) {
Matrix res(d), base = *this;
while (power) {
if (power & 1)
res = res.mul(base, mod);
power >>= 1;
base = base.mul(base, mod);
}
return res;
}
T at(const size_t x, const size_t y) { return mat[x][y]; }
};
using i64 = long long;
using matrix = vector<vector<i64>>;
constexpr i64 mod = 1000000007;rust仿java Scanner的输入
// 输入用
use std::{
io::{stdin, Read},
vec,
};
pub struct Scanner {
stream: std::io::Stdin,
}
impl Scanner {
pub fn new(istream: std::io::Stdin) -> Self {
Self { stream: istream }
}
pub fn skip_line(&mut self) {
let _ = std::io::stdin().read_line(&mut String::new());
}
pub fn read_char(&mut self) -> char {
let mut byte = [0; 1];
let _ = self.stream.read(&mut byte);
return char::from(byte[0]);
}
pub fn next_char(&mut self) -> char {
let mut c: char = self.read_char();
while char::is_whitespace(c) {
c = self.read_char();
}
return c;
}
pub fn next_line(&mut self) -> String {
let mut str = String::new();
let _ = std::io::stdin().read_line(&mut str);
str.pop();
return str;
}
fn read_line_i128(&mut self) -> Vec<i128> {
let mut line = self.next_line();
while line.is_empty() {
line = self.next_line();
}
let inputs: Vec<i128> = line
.trim()
.split_whitespace()
.map(|x| x.parse().expect(""))
.collect();
return inputs;
}
fn read_line_f64(&mut self) -> Vec<f64> {
let mut line = self.next_line();
while line.is_empty() {
line = self.next_line();
}
let inputs: Vec<f64> = line
.trim()
.split_whitespace()
.map(|x| x.parse().expect(""))
.collect();
return inputs;
}
pub fn next_i128(&mut self) -> i128 {
let mut res = 0;
let mut is_negative = false;
let mut chr = self.read_char();
while !char::is_ascii_digit(&chr) {
if chr == '-' {
is_negative = true;
}
chr = self.read_char();
}
while char::is_ascii_digit(&chr) {
res = (res << 3) + (res << 1) + (chr as i128) - ('0' as i128);
chr = self.read_char();
}
return if is_negative { -res } else { res };
}
pub fn next_f64(&mut self) -> f64 {
let mut res = 0.0;
let mut i = 0.0;
let mut is_visted_dot = false;
let mut is_negative = false;
let mut chr = self.read_char();
while !char::is_ascii_digit(&chr) {
if chr == '-' {
is_negative = true;
}
if chr == '.' {
is_visted_dot = true;
}
chr = self.read_char();
}
while char::is_ascii_digit(&chr) && !is_visted_dot {
res = res * 10.0 + ((chr as i128) - ('0' as i128)) as f64;
chr = self.read_char();
}
if chr == '.' {
chr = self.read_char();
}
while char::is_ascii_digit(&chr) {
i = i * 0.1 + ((chr as i128) - ('0' as i128)) as f64;
chr = self.read_char();
}
let res = res + i * 0.1;
return if is_negative { -res } else { res };
}
pub fn next_f32(&mut self) -> f32 {
return self.next_f64() as f32;
}
pub fn next_i64(&mut self) -> i64 {
return self.next_i128() as i64;
}
pub fn next_i32(&mut self) -> i32 {
return self.next_i128() as i32;
}
pub fn next_i16(&mut self) -> i16 {
return self.next_i128() as i16;
}
}普通线段树
template<typename T>
struct SegmentTree {
SegmentTree(std::vector<T> data) : tree(data.size() << 2) {
n = data.size();
build(0, 0, n - 1, data);
}
// [l, r]
T query_range(long l, long r) {
return query_range(0, 0, n - 1, l, r);
}
private:
std::vector<T> tree;
long n;
void build(long index, long l, long r, std::vector<T> &data) {
if (l == r) {
tree[index] = data[l];
return;
}
auto mid = (l + r) >> 1;
auto lkid = index << 1 | 1;
auto rkid = lkid + 1;
build(lkid, l, mid, data);
build(rkid, mid + 1, r, data);
tree[index] = std::max(tree[lkid], tree[rkid]);
}
T query_range(long index, long l, long r, const long ql, const long qr) {
if (ql <= l and r <= qr)
return tree[index];
if (l == r)
return tree[index];
auto mid = (l + r) >> 1;
auto lkid = index << 1 | 1;
auto rkid = lkid + 1;
T result = std::numeric_limits<T>::min();
if (ql <= mid)
result = std::max(result, query_range(lkid, l, mid, ql, qr));
if (qr > mid)
result = std::max(result, query_range(rkid, mid + 1, r, ql, qr));
return result;
}
};zkw线段树
template<class T>
// 写在前头， xor 是 ^ 的别名，bitand 是 & 的别名，bitor 是 | 的别名
class segmentTree {
vector<T> tree, mark;
i64 N; // 子叶节点的个数（不足2的n次幂就补全）
public:
// zkw线段树
explicit segmentTree(const vector<T> &a) {
auto &&n = a.size();
// 补全为 2 的 n 次幂
for (N = 1; N < n; N <<= 1);
// 树和标记要开 2 的 n + 1 次幂的空间（参考满二叉树的节点数）
mark = vector<T>(N << 1, 0);
tree = mark;
// 子叶节点赋值（可以改为直接输入）
for (i64 &&i = 1; i <= n; ++i)
tree[i + N] = a[i - 1];
// 计算每个区间的值，一个区间的和的左孩子区间加右孩子区间
for (i64 i = N - 1; i; --i)
tree[i] = tree[i << 1] + tree[i << 1 bitor 1];
}
// 单点查询
T query_point(const i64 &index) {
// 偷个懒，直接用区间查询来查询单点
return query_range(index, index);
}
// 单点更新
void update_point(const i64 &x, const T &v) {
// 从子叶节点开始回溯到根节点，给他们加上v
for (auto &&i = x + N; i; i >>= 1)
tree[i] += v;
}
// 区间查询
T query_range(i64 l, i64 r) {
// 返回值，当前层任一节点为根的子树的节点数，左、右两边分别实际修改的区间长度
i64 res{0}, cnt{1}, cl{0}, cr{0};
// for(从子叶节点开始回溯（开区间），l + 1 < r，回溯)
for (l += N - 1, r += N + 1; l xor r xor 1; l >>= 1, r >>= 1, cnt <<= 1) {
// 利用标记快速计算
res += cl * mark[l] + cr * mark[r];
// l是偶数，即l是一个节点的左孩子
if (~l bitand 1) {
// 说明它的兄弟（右孩子）对答案有贡献
res += tree[l xor 1];
cl += cnt;
}
// r是奇数，即l是一个节点的右孩子
if (r bitand 1) {
// 说明它的兄弟（左孩子）对答案有贡献
res += tree[r xor 1];
cr += cnt;
}
}
// 回溯中遇到的标记也对答案有相应的贡献，根据查询区间长度计算
for (; l; l >>= 1, r >>= 1)
res += cl * mark[l] + cr * mark[r];
return res;
}
// 区间修改（加）
void update_range(i64 l, i64 r, const T &v) {
i64 cnt{1}, //cnt为以当前层任一节点为根的子树的节点数
cl{0}, cr{0}; //cl, cr 是左、右两边分别实际修改的区间长度
// for(从子叶节点开始回溯（开区间），l + 1 < r，回溯)
for (l += N - 1, r += N + 1; l xor r xor 1; l >>= 1, r >>= 1, cnt <<= 1) {
tree[l] += cl * v; // 更新节点值
tree[r] += cr * v; // 更新节点值
// l是偶数，即l是一个节点的左孩子
if (~l bitand 1) {
// 说明它的兄弟（右孩子）在添加区间内
tree[l xor 1] += cnt * v;
// 标记传递
mark[l xor 1] += v;
cl += cnt;
}
// r是奇数，即l是一个节点的右孩子
if (r bitand 1) {
// 说明它的兄弟（左孩子）在添加区间内
tree[r xor 1] += cnt * v;
// 标记传递
mark[r xor 1] += v;
cr += cnt;
}
}
// 回溯，更新父节点，根据查询区间长度计算
for (; l; l >>= 1, r >>= 1) {
tree[l] += cl * v;
tree[r] += cr * v;
}
}
};kmp系列
// 求next数组
vector<int> getNext(const string &s) {
int n = parse<int>(s.length());
vector<int> next(n, 0);
for (int i = 1, j = 0; i < n; ++i) {
while (j and s[i] != s[j])
j = next[j - 1];
if (s[i] == s[j])
++j;
next[i] = j;
}
return next;
}
// 求原串 container 包含多少个子串 substr
int kmp_counter(const string &container, const string &substr,
auto&& next = vector<int>()) {
if (next.empty())
next = std::move(getNext(substr));
int n = parse<int>(container.length()), m = parse<int>(substr.length()), ans{};
for (int i = 0, j = 0; i < n; ++i) {
while (j and container[i] != substr[j])
j = next[j - 1];
if (container[i] == substr[j])
++j;
if (j == m) {
ans++;
j = 0;
}
}
return ans;
}
// 求原串 container 中子串 substr 出现的第一个位置
size_t kmp_searcher(string &container, const string &substr,
auto&& next = vector<int>(), const int &l = 0) {
if (next.empty())
next = std::move(getNext(substr));
int n = parse<int>(container.length()), m = parse<int>(substr.length());
for (int i = l, j = 0; i < n; ++i) {
while (j and container[i] != substr[j])
j = next[j - 1];
if (container[i] == substr[j])
++j;
if (j == m)
return i - m + 1;
}
return string::npos;
}并查集
template<typename T>
class UnionFindSet {
std::vector<T> trees, size;
public:
explicit UnionFindSet(T len) : trees(len << 1), size((len << 1), 1) {
std::iota(trees.begin(), trees.begin() + len, len);
std::iota(trees.begin() + len, trees.end(), len);
}
T find(const T &x) {
return trees[x] == x ? x : trees[x] = find(trees[x]);
}
void unite(const T &x, const T &y) {
T &&fx = find(x), &&fy = find(y);
if (fx == fy) return;
if (size[fx] < size[fy]) std::swap(fx, fy);
trees[fy] = fx;
size[fx] += size[fy];
}
void erase(const T &x) {
--size[find(x)];
trees[x] = x;
}
void move(const T &x, const T &y) {
T &&fx = find(x), &&fy = find(y);
if (fx == fy) return;
trees[x] = fy;
--size[fx], ++size[fy];
}
bool isSameSet(const T &x, const T &y) {
return find(x) == find(y);
}
};ST表
template<typename T>
class SparseTable {
private:
vector<vector<T> > st;
function<const T &(const T &, const T &)> func;
void init(const vector<T> &input) {
size_t n = input.size() - 1;
st.resize(n + 1);
int m = int(log2(n)) + 2;
for (int i = 0; i <= n; i++) {
st[i].resize(m);
st[i][0] = input[i];
}
for (int j = 1; 1 << j <= n; j++)
for (int i = 1; i + (1 << j) - 1 <= n; i++) {
st[i][j] = func(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
public:
[[maybe_unused]] explicit SparseTable(const vector<T> &input, const bool &isMax = true) {
function<const T &(const T &, const T &)> &&f = [&isMax](const T &a, const T &b) {
return isMax ? max(a, b) : min(a, b);
};
func = f;
init(input);
}
[[maybe_unused]] SparseTable(const vector<T> &input, function<const T &(const T &, const T &)> f) {
func = f;
init(input);
}
[[maybe_unused]] T search(const size_t &l, const size_t &r) {
int k = int(log2(r - l + 1));
return func(st[l][k], st[r - (1 << k) + 1][k]);
}
};Rust Scanner
// 输入用
pub struct Scanner {
stream: std::io::Stdin,
}
impl Scanner {
pub fn new(istream: std::io::Stdin) -> Self {
Self {
stream: istream,
}
}
pub fn skip_line(&mut self) {
let _ = self.stream.read_line(&mut String::new());
}
pub fn read_char(&mut self) -> Option<char> {
let mut byte = [0; 1];
match self.stream.read(&mut byte) {
Ok(0) => None, // EOF
Ok(_) => Some(char::from(byte[0])),
Err(_) => None, // Error reading
}
}
pub fn next_char(&mut self) -> Option<char> {
let mut c = self.read_char()?;
while c.is_whitespace() {
c = self.read_char()?;
}
Some(c)
}
pub fn next(&mut self) -> Option<String> {
let mut c = self.read_char()?;
loop {
if !c.is_whitespace() {
break;
}
c = self.read_char()?;
}
let mut buffer = String::new();
loop {
buffer.push(c);
c = self.read_char()?;
if c.is_whitespace() {
break;
}
}
return if buffer.is_empty() { None } else { Some(buffer) };
}
pub fn next_line(&mut self) -> Option<String> {
let mut buffer = String::new();
match self.stream.read_line(&mut buffer) {
Ok(0) => None, // EOF
Ok(_) => Some(buffer.trim_end().to_string()),
Err(_) => None, // Error reading
}
}
pub fn read_line_i128(&mut self) -> Option<Vec<i128>> {
let line = self.next_line()?;
if line.is_empty() {
return None;
}
let inputs: Vec<i128> = line
.split_whitespace()
.map(|x| x.parse().ok())
.collect::<Option<Vec<i128>>>()?;
Some(inputs)
}
pub fn read_line_f64(&mut self) -> Option<Vec<f64>> {
let line = self.next_line()?;
if line.is_empty() {
return None;
}
let inputs: Vec<f64> = line
.split_whitespace()
.map(|x| x.parse().ok())
.collect::<Option<Vec<f64>>>()?;
Some(inputs)
}
pub fn next_i128(&mut self) -> Option<i128> {
let mut res = 0;
let mut is_negative = false;
let mut chr = self.read_char()?;
while !chr.is_ascii_digit() {
if chr == '-' {
is_negative = true;
}
chr = self.read_char()?;
}
while chr.is_ascii_digit() {
res = (res << 3) + (res << 1) + (chr as i128) - ('0' as i128);
chr = self.read_char()?;
}
Some(if is_negative { -res } else { res })
}
pub fn next_f64(&mut self) -> Option<f64> {
let mut res = 0.0;
let mut i = 0.0;
let mut is_visited_dot = false;
let mut is_negative = false;
let mut chr = self.read_char()?;
while !chr.is_ascii_digit() {
if chr == '-' {
is_negative = true;
}
if chr == '.' {
is_visited_dot = true;
}
chr = self.read_char()?;
}
while chr.is_ascii_digit() && !is_visited_dot {
res = res * 10.0 + ((chr as i128) - ('0' as i128)) as f64;
chr = self.read_char()?;
}
if chr == '.' {
chr = self.read_char()?;
}
while chr.is_ascii_digit() {
i = i * 0.1 + ((chr as i128) - ('0' as i128)) as f64;
chr = self.read_char()?;
}
Some(if is_negative { -res - i } else { res + i })
}
pub fn next_f32(&mut self) -> Option<f32> {
self.next_f64().map(|v| v as f32)
}
pub fn next_i64(&mut self) -> Option<i64> {
self.next_i128().map(|v| v as i64)
}
pub fn next_i32(&mut self) -> Option<i32> {
self.next_i128().map(|v| v as i32)
}
pub fn next_i16(&mut self) -> Option<i16> {
self.next_i128().map(|v| v as i16)
}
}好用的模板
https://winterl-blog.netlify.app/2024/11/18/好用的模板/