并查集
struct DSU {
std::vector<int> f, siz;
DSU() {}
DSU(int n) {
init(n);
}
void init(int n) {
f.resize(n);
std::iota(f.begin(), f.end(), 0);
siz.assign(n, 1);
}
int find(int x) {
while (x != f[x]) {
x = f[x] = f[f[x]];
}
return x;
}
bool same(int x, int y) {
return find(x) == find(y);
}
bool merge(int x, int y) {
x = find(x);
y = find(y);
if (x == y) {
return false;
}
siz[x] += siz[y];
f[y] = x;
return true;
}
int size(int x) {
return siz[find(x)];
}
};
树状数组
struct FenwickTree {
vector<int> tree;
int n;
FenwickTree() {}
FenwickTree(int n) {
init(n);
}
void init(int n) {
this->n = n;
tree.resize(n + 1, 0);
}
int lowbit(int x) {
return x & -x;
}
void update(int x, int k) {
while (x <= n) {
tree[x] += k;
x += lowbit(x);
}
}
int query(int x) {
int res = 0;
while (x > 0) {
res += tree[x];
x -= lowbit(x);
}
return res;
}
int query(int l, int r) {
return query(r) - query(l - 1);
}
};
类欧几里德算法解决Floor_Sum问题
问题解析
constexpr long long MOD = 998244353;
constexpr long long INV_2 = 499122177; // 2的逆元
constexpr long long INV_6 = 166374059; // 6的逆元
struct Floor_sum {
long long f, g, h; // 三个函数值
Floor_sum(long long f = 0, long long g = 0, long long h = 0) : f(f), g(g), h(h) {}
// 重载加法运算符，方便合并结果
Floor_sum operator+(const Floor_sum& other) const {
return Floor_sum((f + other.f), (g + other.g), (h + other.h));
}
};
// 单独封装 f 的计算逻辑
long long calculate_f(long long n, long long a, long long b, long long c, bool is_mod = true) {
if (a == 0) {
return is_mod ? ((b / c) * (n + 1) % MOD) : ((b / c) * (n + 1));
}
if (a >= c || b >= c) {
long long ac = a / c, bc = b / c;
long long base_f = is_mod ? ((ac * n % MOD * (n + 1) % MOD * INV_2 + bc * (n + 1)) % MOD) : (ac * n * (n + 1) / 2 + bc * (n + 1));
return is_mod ? ((base_f + calculate_f(n, a % c, b % c, c, true)) % MOD) : (base_f + calculate_f(n, a % c, b % c, c, false));
}
long long m = (a * n + b) / c;
return is_mod ? ((n * m % MOD - calculate_f(m - 1, c, c - b - 1, a, true) + MOD) % MOD) : (n * m - calculate_f(m - 1, c, c - b - 1, a, false));
}
// 封装 g 和 h 的计算逻辑，依赖 f 的结果
Floor_sum calculate_gh(long long n, long long a, long long b, long long c, long long f, bool is_mod = true) {
if (a == 0) {
long long bc = b / c;
return is_mod ? Floor_sum(bc * n % MOD * (n + 1) % MOD * INV_2 % MOD, bc * bc % MOD * (n + 1) % MOD) : Floor_sum(bc * n * (n + 1) / 2, bc * bc * (n + 1));
}
if (a >= c || b >= c) {
long long ac = a / c, bc = b / c;
Floor_sum base(is_mod ? (ac * n % MOD * (n + 1) % MOD * (2 * n + 1) % MOD * INV_6 % MOD + bc * n % MOD * (n + 1) % MOD * INV_2 % MOD) : (ac * n * (n + 1) * (2 * n + 1) / 6 + bc * n * (n + 1) / 2),
is_mod ? (ac * ac % MOD * n % MOD * (n + 1) % MOD * (2 * n + 1) % MOD * INV_6 % MOD + bc * bc % MOD * (n + 1) % MOD + ac * bc % MOD * n % MOD * (n + 1) % MOD) : (ac * ac * n * (n + 1) * (2 * n + 1) / 6 + bc * bc * (n + 1) + ac * bc * n * (n + 1)));
Floor_sum recursive = calculate_gh(n, a % c, b % c, c, f, is_mod);
return is_mod ? Floor_sum((base.g + recursive.g) % MOD, (base.h + recursive.h + 2 * bc % MOD * recursive.f % MOD + 2 * ac % MOD * recursive.g % MOD) % MOD) : Floor_sum(base.g + recursive.g, base.h + recursive.h + 2 * bc * recursive.f + 2 * ac * recursive.g);
}
long long m = (a * n + b) / c;
Floor_sum recursive = calculate_gh(m - 1, c, c - b - 1, a, f, is_mod);
return is_mod ? Floor_sum((m * n % MOD * (n + 1) % MOD - recursive.h - recursive.f + MOD) % MOD * INV_2 % MOD,
(n * m % MOD * (m + 1) % MOD - 2 * recursive.g - 2 * recursive.f - recursive.f + MOD) % MOD) : Floor_sum((m * n * (n + 1) - recursive.h - recursive.f) / 2,
n * m * (m + 1) - 2 * recursive.g - 2 * recursive.f - recursive.f);
}
// 主计算函数，整合 f、g、h 的计算
Floor_sum calculate(long long n, long long a, long long b, long long c, bool is_mod = true) {
long long f = calculate_f(n, a, b, c, is_mod);
Floor_sum gh = calculate_gh(n, a, b, c, f, is_mod);
return Floor_sum(f, gh.g, gh.h);
}
最大流
const int INF = 1e9 + 10;
const ll INF_LL = 4e18;
// 最大流 Dinic 算法实现
struct MXF {
struct Edge {
int from, to, rev; // 边的起点、终点和反向边索引
ll cap, flow; // 边的容量和流量
bool isrev; // 是否是反向边
Edge(int from, int to, ll cap, int rev, bool isrev)
: from(from), to(to), rev(rev), cap(cap), flow(0), isrev(isrev) {}
};
vector<vector<Edge>> graph; // 邻接表
vector<int> level, iter; // BFS 层次和 DFS 当前弧
// 构造函数，初始化图
MXF(int n) : graph(n), level(n), iter(n) {}
// 添加边
void add_edge(int from, int to, ll cap) {
graph[from].emplace_back(from, to, cap, graph[to].size(), false);
graph[to].emplace_back(to, from, 0, graph[from].size() - 1, true);
}
// BFS 构建层次图
void bfs(int s) {
fill(level.begin(), level.end(), -1);
queue<int> q;
level[s] = 0;
q.push(s);
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto &e : graph[v]) {
if (e.cap > 0 && level[e.to] < 0) {
level[e.to] = level[v] + 1;
q.push(e.to);
}
}
}
}
// DFS 寻找增广路径
ll dfs(int v, int t, ll f) {
if (v == t) return f;
for (int &i = iter[v]; i < graph[v].size(); ++i) {
Edge &e = graph[v][i];
if (e.cap > 0 && level[v] < level[e.to]) {
ll d = dfs(e.to, t, min(f, e.cap));
if (d > 0) {
e.cap -= d;
graph[e.to][e.rev].cap += d;
e.flow += d;
graph[e.to][e.rev].flow -= d;
return d;
}
}
}
return 0;
}
// 计算从源点 s 到汇点 t 的最大流
ll flow(int s, int t) {
ll ret = 0;
while (true) {
bfs(s);
if (level[t] < 0) return ret; // 如果汇点不可达，结束算法
fill(iter.begin(), iter.end(), 0);
ll f;
while ((f = dfs(s, t, INF_LL)) > 0) ret += f;
}
}
// 获取最小割
vector<bool> mincut(int v = 0) {
vector<bool> ret(graph.size());
queue<int> q;
q.push(v);
ret[v] = true;
while (!q.empty()) {
int v = q.front();
q.pop();
for (auto &e : graph[v]) {
if (e.cap > 0 && !ret[e.to]) {
ret[e.to] = true;
q.push(e.to);
}
}
}
return ret;
}
// 获取所有边的信息
vector<Edge> get_edges() {
vector<Edge> ret;
for (int i = 0; i < graph.size(); ++i) {
for (auto &e : graph[i]) {
if (e.isrev) continue;
ret.push_back(e);
}
}
return ret;
}
};
最小费用流
const int INF = 1e9 + 10;
const ll INF_LL = 4e18;
// 最小費用流
// 支持负权边，但不允许存在负环。
struct MCF {
struct Edge {
int from, to, rev;
ll cap, cost;
bool isrev;
Edge(int from, int to, ll cap, ll cost, int rev, bool isrev) : from(from), to(to), cap(cap), cost(cost), rev(rev), isrev(isrev) {}
};
vector<vector<Edge>> graph;
vector<ll> dist, pot; // dist: 最短距离，pot: 势能函数
vector<int> pv, pe;
MCF(int n) { graph.resize(n), dist.resize(n), pot.resize(n), pv.resize(n), pe.resize(n); }
// 添加边
// 增加一条从 from 到 to 的边，容量为 cap，费用为 cost
// cost 可以为负，但图中不能有负环
void add_edge(int from, int to, ll cap, ll cost) {
graph[from].push_back(Edge(from, to, cap, cost, graph[to].size(), false));
graph[to].push_back(Edge(to, from, 0, -cost, (int)graph[from].size() - 1, true));
}
// 获取所有边的信息
vector<Edge> get_edges() {
vector<Edge> ret;
for (int i = 0; i < (int)graph.size(); i++)
for (auto &e : graph[i])
if (!e.isrev) ret.push_back(e);
return ret;
}
// 计算最小费用流
// 从源点 s 到汇点 t，寻找流量为 f 的最小费用流
// 如果无法满足流量 f，则返回 INFL 表示无解
// 时间复杂度：O(FE log V)，其中 F 是流量，E 是边数，V 是顶点数
ll flow(int s, int t, ll f) {
int n = graph.size();
priority_queue<pair<ll, int>, vector<pair<ll, int>>, greater<pair<ll, int>>> pq;
fill(pot.begin(), pot.end(), 0), fill(pv.begin(), pv.end(), 0), fill(pe.begin(), pe.end(), 0);
ll ret = 0;
while (f > 0) {
fill(dist.begin(), dist.end(), INF_LL);
dist[s] = 0;
pq.push({0, s});
while (!pq.empty()) {
auto [tmp, now] = pq.top();
pq.pop();
if (dist[now] < tmp) continue;
for (int i = 0; i < (int)graph[now].size(); i++) {
auto [from, to, rev, cap, cost, isrev] = graph[now][i];
ll ncost = dist[now] + cost + pot[now] - pot[to];
if (cap > 0 && dist[to] > ncost) {
dist[to] = ncost, pv[to] = now, pe[to] = i;
pq.push({dist[to], to});
}
}
}
if (dist[t] == INF_LL) return INF_LL;
for (int i = 0; i < n; i++) pot[i] += dist[i];
ll d = f;
for (int v = t; v != s; v = pv[v]) d = min(d, graph[pv[v]][pe[v]].cap);
f -= d, ret += d * pot[t];
for (int v = t; v != s; v = pv[v]) {
auto &e = graph[pv[v]][pe[v]];
e.cap -= d, graph[v][e.rev].cap += d;
}
}
return ret;
}
};
卷积
const int INF = 1e9 + 10;
const ll INFL = 4e18;
template <ll MOD>
struct ModInt {
ll value;
ModInt(ll x = 0) { value = (x >= 0 ? x % MOD : MOD - (-x) % MOD); }
ModInt operator-() const { return ModInt(-value); }
ModInt operator+() const { return ModInt(*this); }
ModInt& operator+=(const ModInt& other) {
value += other.value;
if (value >= MOD) value -= MOD;
return *this;
}
ModInt& operator-=(const ModInt& other) {
value += MOD - other.value;
if (value >= MOD) value -= MOD;
return *this;
}
ModInt& operator*=(const ModInt other) {
value = value * other.value % MOD;
return *this;
}
ModInt& operator/=(ModInt other) {
(*this) *= other.inv();
return *this;
}
ModInt operator+(const ModInt& other) const { return ModInt(*this) += other; }
ModInt operator-(const ModInt& other) const { return ModInt(*this) -= other; }
ModInt operator*(const ModInt& other) const { return ModInt(*this) *= other; }
ModInt operator/(const ModInt& other) const { return ModInt(*this) /= other; }
ModInt pow(ll x) const {
ModInt ret(1), mul(value);
while (x) {
if (x & 1) ret *= mul;
mul *= mul;
x >>= 1;
}
return ret;
}
ModInt inv() const { return pow(MOD - 2); }
bool operator==(const ModInt& other) const { return value == other.value; }
bool operator!=(const ModInt& other) const { return value != other.value; }
friend ostream& operator<<(ostream& os, const ModInt& x) { return os << x.value; }
friend istream& operator>>(istream& is, ModInt& x) {
ll v;
is >> v;
x = ModInt<MOD>(v);
return is;
}
static constexpr ll get_mod() { return MOD; }
};
using Mod998 = ModInt<998244353>;
using Mod107 = ModInt<1000000007>;
vector<Mod998> NTT998(vector<Mod998> a, bool inv = false) {
int n = a.size(), h = 0;
while ((1 << h) < n) h++;
for (int i = 0; i < n; i++) {
int j = 0;
for (int k = 0; k < h; k++) j |= (i >> k & 1) << (h - 1 - k);
if (i < j) swap(a[i], a[j]);
}
const vector<Mod998> rt = {1, 998244352, 911660635, 372528824, 929031873, 452798380, 922799308, 781712469, 476477967, 166035806, 258648936, 584193783, 63912897, 350007156, 666702199, 968855178, 629671588, 24514907, 996173970, 363395222, 565042129, 733596141, 267099868, 15311432};
const vector<Mod998> irt = {1, 998244352, 86583718, 509520358, 337190230, 87557064, 609441965, 135236158, 304459705, 685443576, 381598368, 335559352, 129292727, 358024708, 814576206, 708402881, 283043518, 3707709, 121392023, 704923114, 950391366, 428961804, 382752275, 469870224};
for (int b = 1, t = 1; b < n; b <<= 1, t++) {
Mod998 w = 1, base = inv ? irt[t] : rt[t];
for (int j = 0; j < b; j++) {
for (int k = 0; k < n; k += b * 2) {
Mod998 s = a[j + k];
Mod998 t = a[j + k + b] * w;
a[j + k] = s + t;
a[j + k + b] = s - t;
}
w *= base;
}
}
if (inv) {
Mod998 inv_n = Mod998(n).inv();
for (int i = 0; i < n; i++) a[i] *= inv_n;
}
return a;
}
vector<Mod998> convolve998(vector<Mod998> a, vector<Mod998> b) {
int n = 1;
while (n < (int)a.size() + (int)b.size() - 1) n <<= 1;
vector<Mod998> fa(n), fb(n);
for (int i = 0; i < (int)a.size(); i++) fa[i] = a[i];
for (int i = 0; i < (int)b.size(); i++) fb[i] = b[i];
fa = NTT998(fa), fb = NTT998(fb);
for (int i = 0; i < n; i++) fa[i] *= fb[i];
fa = NTT998(fa, true);
while ((int)fa.size() > (int)a.size() + (int)b.size() - 1) fa.pop_back();
return fa;
}
void solve() {
int n, m;
cin >> n >> m;
vector<Mod998> a(n), b(m);
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < m; i++) cin >> b[i];
for (auto x : convolve998(a, b)) cout << x << " ";
cout << endl;
}
