A 小月的前缀（构造version）
题目要求 $A_r$ 的得分严格最大。
我们可以尝试一种极端的构造策略：让 $A_r$ 的得分为 $\text{1}$ ，而让其他所有 $A_s$ ($s \neq r$) 的得分都为 $\text{0}$ 。
时间复杂度：$O(n)$
评分：$\text{800}$
void solve() {
int n, r;
cin >> n >> r;
for (int i = 1; i <= n; ++i) cout << (i == r + 1 ? 1 : -1000000000) << " ";
cout << "\n";
}B 小月的排序
任意正整数 $n$ 都可以唯一分解为 $n=s^2\times k$ ，其中 $k$ 是不含平方因子的整数（即 $k$ 的质因数分解中所有质数的指数都为 1），我们称 $k$ 为 $n$ 的无平方因子部分，记作 $core(n)$ 。
两数乘积为：$x\times y = (s_x^2\cdot core(x))\times(s_y^2\cdot core(y)) = (s_x^2\cdot s_y^2)\times(core(x)\cdot core(y))$
要使 $x\times y$ 是完全平方数，必须满足 $core(x)\cdot core(y)$ 是完全平方数。由于 $core(x)$ 和 $core(y)$ 都不含平方因子，唯一的可能是 $core(x)=core(y)$ 。
这意味着，数组中的元素被分成了若干个部分。同一个部分内的数字可以任意交换位置，但不同部分的数字无法交换位置。
原数组 $A$ 在位置 $i$ 上的数 $A_i$ ，如果想要移动到它在有序数组中的正确位置，或者说，有序数组 $B$ 在位置 $i$ 上的数 $B_i$ 想要能够来到这个位置，它们必须属于同一个部分。
换句话说，对于每一个位置 $i$ ，原数组该位置的数 $A_i$ 必须和排序后该位置的数 $B_i$ 能够发生交换。
即：对于所有 $0\leq i<n$ ，必须满足 $core(A_i)=core(B_i)$ ，等价于判断 $A_i\times B_i$ 是否为完全平方数。
时间复杂度：$O(nlogn)$
评分：$\text{1100}$
void solve() {
int n;
cin >> n;
vector<ll> a(n);
for (int i = 0; i < n; ++i) cin >> a[i];
auto b = a;
sort(all(a));
for (int i = 0; i < n; ++i) {
ll t = sqrt(a[i] * b[i]);
if (t * t != a[i]*b[i]) {
cout << "NO" << "\n";
return;
}
}
cout << "YES" << "\n";
}C 小月的计数
- 左半部分：对于所有的 $x\in [0,m−1]$ ，计算 $x^A \pmod m$ 的值。我们可以统计每一个余数 $v$ 在左边出现的次数，记为 $cntA[v]$ 。
- 右半部分：对于所有的 $y\in[0,m−1]$ ，计算 $y^B \pmod m$ 的值。同样统计每一个余数 $v$ 在右边出现的次数，记为 $cntB[v]$ 。
那么根据乘法原理，使得等式两边都等于 $t$ 的 $(x,y)$ 组合共有 $cntA[t]\times cntB[t]$ 对。
时间复杂度：$O(m·(logA+logB))$
评分：$\text{1200}$
void solve() {
ll a, b;
int m;
cin >> a >> b >> m;
vector<ll> cntA(m), cntB(m);
Z::setMod(m);
for (int i = 0; i < m; ++i) {
Z r = ksm(Z(i), a);
cntA[r.val()]++;
r = ksm(Z(i), b);
cntB[r.val()]++;
}
ll ans = 0;
for (int i = 0; i < m; ++i) {
ans += cntA[i] * cntB[i];
}
cout << ans << "\n";
}D 小月的前缀
原数组的前缀和数组为 $S$ ，即 $S_i=\sum\limits_{k=1}^{i}a_k ( S_0=0)$ 。
为了方便处理循环移位，我们将原数组复制一份接在后面，形成长度为 $2n$ 的数组。记在这个扩展数组上的前缀和为 $S′$ 。
即 $Si′$ 表示扩展数组前 $i$ 个元素的和。
对于偏移量 $r(0\leq r<n)$ ，移位后的数组实际上对应扩展数组中下标从 $r+1$ 开始、长度为 $n$ 的子段。
移位后数组的第 $k$ 个前缀和可以表示为：
$Pre(r)=S_{r+k}′−S_r′$
前缀和 $>0$ 的数量，即满足：$S_{r+k}′−S_r′>0⟺S_{r+k}′>Sr′$
其中 $1\leq k\leq n$ 。
对于每一个偏移量 $r$ ，我们需要在滑动窗口 ${S_{r+1}′,S_{r+2}′,…,S_{r+n}′}$ 中，统计有多少个元素严格大于基准值 $S_r′$ 。
由于数组下标较大，所以需要离散化。
时间复杂度：$O(nlogn)$
评分：$\text{1600}$
void solve() {
int n;
cin >> n;
vector<ll> a(n + 1);
for (int i = 1; i <= n; i++) cin >> a[i], a.pb(a[i]);
for (int i = 1; i <= n * 2; i++) a[i] += a[i - 1];
auto b = a;
sort(all(b));
b.erase(unique(all(b)), b.end());
for (int i = 0; i <= n * 2; i++) a[i] = lower_bound(all(b), a[i]) - b.begin() + 1;
BIT<int> F(n * 2 + 1);
int ans = 0, cnt = 0;
for (int i = 1; i <= n; i++) F.add(a[i], 1);
for (int i = 1; i <= n; i++) {
int res = n - F.ask(a[i - 1]);
if (res > ans) {
ans = res;
cnt = i - 1;
}
F.add(a[i], -1);
F.add(a[i + n], 1);
}
cout << cnt << " " << ans << endl;
}E 小月的交换
交换相邻边的标记，实际上相当于让标记 $\text{1}$ 在图的边上移动。
- 例如，边 $(u,v)$ 有 $\text{1}$ ，边 $(v,w)$ 有 $\text{0}$ 。交换后，$\text{1}$ 从 $(u,v)$ 移动到了 $(v,w)$ 。这一步操作经过了公共顶点 $v$ ，花费代价为 $\text{1}$ 。
操作只是移动 $\text{1}$ ，不会产生或消失 $\text{1}$ 。因此，若 $x$ 中 $\text{1}$ 的数量与 $y$ 中不同，直接输出 $\text{NO}$ 。
我们需要将所有“多余的 $\text{1}$”（即 $x_i=1,y_i=0$ 的边）移动到“缺少的 $\text{1}$”（即 $x_j=0,y_j=1$ 的边）的位置上。
这就变成了一个 二分图最小权匹配 或 最小费用最大流 问题。
需要注意的是，从一条边 $i$ 移动到相邻边 $j$（假设它们在原图中通过顶点 $u$ 相连），路径是：$\text{边节点i}\rightarrow\text{顶点节点u}\rightarrow\text{边节点j}$ 。
此时的费用为 $1+1=2$ ，但是实际一次交换代价为 $\text{1}$ ，所以记得除以 $\text{2}$ 。
时间复杂度：$O(K·ElogV)$
评分：$\text{2100}$
void solve() {
int n, m;
cin >> n >> m;
int S = m + n;
int T = m + n + 1;
MinCostFlow<ll> mcf(T + 2);
vector<PII> edges(m);
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
u--, v--;
mcf.addEdge(i, m + u, INF, 1);
mcf.addEdge(m + u, i, INF, 1);
mcf.addEdge(i, m + v, INF, 1);
mcf.addEdge(m + v, i, INF, 1);
}
string x, y;
cin >> x >> y;
int cx = 0, cy = 0, su = 0;;
for (char c : x) if (c == '1') cx++;
for (int i = 0; i < m; ++i) {
if (y[i] == '1') cy++;
if (x[i] == '1' && y[i] == '0') {
mcf.addEdge(S, i, 1, 0);
su++;
}
if (x[i] == '0' && y[i] == '1') {
mcf.addEdge(i, T, 1, 0);
}
}
if (cx != cy) {
cout << "NO" << "\n";
return;
}
PLL res = mcf.flow(S, T);
if (res.fi != su) {
cout << "NO" << "\n";
} else {
cout << "YES" << "\n";
cout << res.se / 2 << "\n";
}
}F 小月的色图
不同颜色的边互不干扰。我们可以分别处理每一种颜色，判断该颜色在哪些时间段内是二分图，哪些时间段内不是。
我们可以建立一个全局的数据结构，初始时认为所有 $c$ 种颜色在所有时间点都是二分图（值为 $c$）。当我们检测到某种颜色 $k$ 在时间段 $[L,R]$ 内不是二分图时，我们将该时间段的答案减 $\text{1}$ 。
对于动态的“插入/删除”操作，我们可以将其转化为“边存在的时间区间”。
- 例如，一条边在第 $\text{3}$ 次操作被插入，第 $\text{8}$ 次操作被删除，则它存在于时间区间 $[3,7]$ 。
- 这样，问题就变成了：给定若干个带有时间区间的边，判断每个时刻图是否为二分图。
对于这种“允许离线、支持边的删除”的动态图问题，我们采用线段树分治。
我们对操作的时间轴 $[1,q]$ 建树。树上的每个节点代表一个时间区间 $[l,r]$ 。
将每一条边（根据其存在的时间区间）挂载到时间线段树的对应节点上。如果一条边存在于 $[3,7]$ ，它会被挂载到覆盖 $[3,7]$ 的 $\text{O(logq)}$ 个线段树节点上。
从根节点开始遍历整棵树：
- 进入节点：将挂载在该节点上的所有边加入图（使用并查集 $\text{DSU}$ ）。
- 判定与剪枝：检查当前颜色是否出现了奇环（二分图判定条件）。
- 如果出现奇环，说明在该节点覆盖的整个时间区间 $[l,r]$ 内，该颜色都不是二分图。
- 直接在全局答案线段树上对 $[l,r]$ 区间减 1。
- 剪枝：既然已经有奇环，添加更多边也不可能消除奇环，因此不需要继续递归子节点，直接返回。
- 递归：如果当前没有奇环，且 $l\neq r$ ，则递归处理左右子节点。
- 回溯：离开节点时，将步骤 1 中加入的边从 $\text{DSU}$ 中撤销，恢复现场。
奇环判定：
- 将每个点 $u$ 拆成两个点 $u$ 和 $u+n$ 。
- 连边 $(u,v)$ 时，合并 $(u,v+n)$ 和 $(u+n,v)$ 。
- 如果 $u$ 和 $u+n$ 在同一个集合中，说明存在奇环，图不是二分图。
时间复杂度：$O((m+q)logqlogn)$
评分：$\text{2400}$
struct Edge {
int u, v, l, r;
};
void solve() {
int n, m, c, q;
cin >> n >> m >> c >> q;
vector<vector<Edge>> edge(c + 1);
map<TIII, int> st;
for (int i = 0; i < m; ++i) {
int u, v, c;
cin >> u >> v >> c;
st[ {u, v, c}] = 1;
}
vector<bool> qry(q + 1);
for (int i = 1; i <= q; ++i) {
char op;
cin >> op;
if (op == 'T') {
int u, v, k;
cin >> u >> v >> k;
if (st.count({u, v, k})) {
auto it = st.find({u, v, k});
if (it != st.end()) {
edge[k].pb({u, v, it->se, i - 1});
}
st.erase(it);
} else {
st[ {u, v, k}] = i;
}
} else {
qry[i] = 1;
}
}
for (auto [key, ST] : st) {
auto [u, v, k] = key;
edge[k].pb({u, v, ST, q});
}
SegTree<int> seg(q);
vector<int> init(q + 1, c);
seg.build(init);
DSU dsu(2 * n);
function<void(int, int, vector<Edge>)> ssolve = [&](int l, int r, vector<Edge> edges) {
if (edges.empty()) return;
int tm = dsu.time();
vector<Edge> L, R;
int mid = (l + r) >> 1;
bool f = false;
for (auto e : edges) {
if (e.l <= l && e.r >= r) {
int u = e.u, v = e.v;
dsu.merge(u, v + n);
dsu.merge(u + n, v);
if (dsu.same(u, u + n)) {
f = true;
break;
}
} else {
if (e.l <= mid) L.pb(e);
if (e.r > mid) R.pb(e);
}
}
if (f) {
Tag<int> t; t.v = -1;
seg.update(l, r, t);
} else {
if (l != r) {
ssolve(l, mid, L);
ssolve(mid + 1, r, R);
}
}
dsu.revert(tm);
};
for (int i = 1; i <= c; ++i) {
if (!edge[i].empty()) {
ssolve(1, q, edge[i]);
}
}
for (int i = 1; i <= q; ++i) {
if (qry[i]) cout << seg.ask(i, i).val << "\n";
}
}G 小月的炼金术
求生成树权值之和，我们很容易想到使用矩阵树定理：图的生成树权值之和等于其基尔霍夫矩阵（即度数矩阵减去邻接矩阵）的任意一个 $(n−1)\times (n−1)$ 主子式的行列式。
标准的矩阵树定理计算的是所有生成树的权值和，无法直接过滤出满足特定计数条件的生成树。
这里的约束条件涉及 $\pmod 3$ 。处理模 $k$ 的计数问题，常用的技巧是单位根反演。
我们可以给每条边赋予一个额外的多项式变量 $x$ 的指数：
- 火元素：贡献 $\text{+1}$ ，对应权值 $w_i\cdot x^1$ 。
- 冰元素：贡献 $\text{−1}$ ，对应权值 $w_i\cdot x^{−1}$ 。
- 普通元素：贡献 $\text{0}$ ，对应权值 $w_i\cdot x^0$ 。
如果我们能计算出多项式 $S(x) = \sum_{\mathcal{T}}(\prod_{e\in{\mathcal{T}}}\mathcal{w}_e)x^{(cnt_0-cnt_1)}$ ，那么我们要求的答案就是 $S(x)$ 中 $x$ 的指数为 $3k$ 的项的系数之和。
利用 $3$ 次单位根 $\omega=e^{i\frac{2\pi}{3}}$ 的性质：$\sum_{j=0}^2(\omega^k)^j=\begin{cases}3, & x\equiv0\pmod 3 \\0, & k \not\equiv 0\pmod 3\end{cases}$ 。
我们只需要分别计算 $x=1,x=\omega,x=\omega^2$ 时代入基尔霍夫矩阵求出的行列式值 $S(1),S(\omega),S(\omega^2)$ ，然后计算：
$$Ans=\frac{S(1)+S(\omega)+S(\omega^2)}{3}$$
由于是在模 $998244353$ 下进行运算，我们需要处理复数 $\omega$ 。
定义 $\omega$ 满足 $\omega^2+\omega+1=0$ ，即 $\omega^2=−1−\omega$ 。
我们可以定义一种类似于复数的结构 $Complex3$ ，形如 $a+b\omega$ ，其中 $a,b$ 为模 $P$ 下的整数。
- 加法：$(a+b\omega)+(c+d\omega)=(a+c)+(b+d)\omega$
- 乘法：利用 $\omega^2=−1−\omega$ 展开。 $(a+b\omega)(c+d\omega)=ac+(ad+bc)\omega+bd\omega^2=(ac−bd)+(ad+bc−bd)\omega$ 。
- 除法（求逆）：需要计算模长：$N(a+b\omega)=a^2−ab+b^2$ 。
时间复杂度：$O(n^3)$
评分：$\text{2300}$
struct Edge {
int u, v;
Z w;
int type;
};
void solve() {
int n, m;
cin >> n >> m;
vector<Edge> E(m);
for (int i = 0; i < m; i++) {
cin >> E[i].u >> E[i].v >> E[i].w >> E[i].type;
E[i].u--;
E[i].v--;
}
Complex3<Z> w0(1, 0);
Complex3<Z> w1(0, 1);
Complex3<Z> w2 = w1 * w1;
Matrix<Complex3<Z>> mat(3, 3);
mat[0][0] = w0; mat[0][1] = w0; mat[0][2] = w0;
mat[1][0] = w1; mat[1][1] = w2; mat[1][2] = w0;
mat[2][0] = w2; mat[2][1] = w1; mat[2][2] = w0;
Complex3<Z> sum(0, 0);
for (int j = 0; j < 3; j++) {
Matrix<Complex3<Z>> L(n - 1, n - 1);
for (const auto& e : E) {
Complex3<Z> weight(e.w, 0);
weight *= mat[j][e.type];
if (e.u < n - 1 && e.v < n - 1) {
L[e.u][e.v] -= weight;
L[e.v][e.u] -= weight;
}
if (e.u < n - 1) L[e.u][e.u] += weight;
if (e.v < n - 1) L[e.v][e.v] += weight;
}
Complex3<Z> det = determinant(n - 1, L);
sum += det;
}
Z ans = sum.a / 3;
cout << ans << endl;
}头文件
//Another
#include<bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define fi first
#define se second
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
using namespace std;
using ll = long long;
using ld = long double;
using ull = unsigned long long;
using i128 = __int128;
using PII = pair<int, int>;
using PLL = pair<ll, ll>;
using TIII = tuple<int, int, int>;
using TLLL = tuple<ll, ll, ll>;
constexpr int inf = (ll)1e9 + 7;
constexpr ll INF = (ll)2e18 + 9;
// constexpr ll INF = (ll)4e18;
// constexpr ll MOD = 1e9 + 7;
constexpr ll MOD = 998244353;
constexpr ld eps = 1e-10;
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
ull randint(ull l, ull r) {uniform_int_distribution<unsigned long long> dist(l, r); return dist(rng);}
void init() {
}
void solve() {
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
init();
int t = 1;
cin >> t;
for (int _ = 1; _ <= t; ++_) {
solve();
}
return 0;
}自动取模
template<class T>
constexpr T ksm(T a, ll b) {
T res = 1;
while (b) {
if (b & 1) res *= a;
b >>= 1;
a *= a;
}
return res;
}
template<int P>
struct MInt {
int x;
constexpr MInt(): x() {}
constexpr MInt(ll x) : x{norm(x % getMod())} {}
static int Mod;
constexpr static int getMod() {
if (P > 0) {
return P;
} else {
return Mod;
}
}
constexpr static void setMod(int Mod_) {
Mod = Mod_;
}
constexpr int norm(int x) const {
if (x < 0) {
x += getMod();
}
if (x >= getMod()) {
x -= getMod();
}
return x;
}
constexpr int val() const {
return x;
}
explicit constexpr operator int() const {
return x;
}
constexpr MInt operator-() const {
MInt res;
res.x = norm(getMod() - x);
return res;
}
constexpr MInt inv() const {
assert(x != 0);
return ksm(*this, getMod() - 2);
}
constexpr MInt &operator*=(MInt rhs) & {
x = 1LL * x * rhs.x % getMod();
return *this;
}
constexpr MInt &operator+=(MInt rhs) & {
x = norm(x + rhs.x);
return *this;
}
constexpr MInt &operator-=(MInt rhs) & {
x = norm(x - rhs.x);
return *this;
}
constexpr MInt &operator/=(MInt rhs) & {
return *this *= rhs.inv();
}
friend constexpr MInt operator*(MInt lhs, MInt rhs) {
MInt res = lhs;
res *= rhs;
return res;
}
friend constexpr MInt operator+(MInt lhs, MInt rhs) {
MInt res = lhs;
res += rhs;
return res;
}
friend constexpr MInt operator-(MInt lhs, MInt rhs) {
MInt res = lhs;
res -= rhs;
return res;
}
friend constexpr MInt operator/(MInt lhs, MInt rhs) {
MInt res = lhs;
res /= rhs;
return res;
}
friend constexpr istream &operator>>(istream &is, MInt &a) {
ll v;
is >> v;
a = MInt(v);
return is;
}
friend constexpr ostream &operator<<(ostream &os, const MInt &a) {
return os << a.val();
}
friend constexpr bool operator==(MInt lhs, MInt rhs) {
return lhs.val() == rhs.val();
}
friend constexpr bool operator!=(MInt lhs, MInt rhs) {
return lhs.val() != rhs.val();
}
};
template<>
int MInt<0>::Mod = 998244353;
template<int V, int P>
constexpr MInt<P> CInv = MInt<P>(V).inv();
// using Z = MInt<MOD>;
using Z = MInt<0>;树状数组
template<class Int>
struct BIT {
vector<Int> a;
int n;
BIT() {}
BIT(int n) {
init(n);
}
void init(int n) {
this->n = n;
a.resize(n + 1);
}
void add(int x, int k) {
for (; x <= n; x += x & -x) {
a[x] += k;
}
}
void add(int x, int y, Int k) {
add(x, k), add(y + 1, -k);
}
Int ask(int x) {
Int ans = 0;
for (; x; x -= x & -x) {
ans += a[x];
}
return ans;
}
Int ask(int x, int y) {
return ask(y) - ask(x - 1);
}
Int kth(int k) {
Int ans = 0;
for (int i = __lg(n); i >= 0; i--) {
Int val = ans + (1 << i);
if (val < n && a[val] < k) {
k -= a[val];
ans = val;
}
}
return ans + 1;
}
};最小费用最大流
template<class T>
struct MinCostFlow {
struct _Edge {
int to;
T cap;
T cost;
_Edge(int to_, T cap_, T cost_) : to(to_), cap(cap_), cost(cost_) {}
};
int n;
vector<_Edge> e;
vector<vector<int>> g;
vector<T> h, dis;
vector<int> pre;
bool dijkstra(int s, int t) {
dis.assign(n, numeric_limits<T>::max());
pre.assign(n, -1);
priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> que;
dis[s] = 0;
que.emplace(0, s);
while (!que.empty()) {
T d = que.top().first;
int u = que.top().second;
que.pop();
if (dis[u] != d) {
continue;
}
for (int i : g[u]) {
int v = e[i].to;
T cap = e[i].cap;
T cost = e[i].cost;
if (cap > 0 && dis[v] > d + h[u] - h[v] + cost) {
dis[v] = d + h[u] - h[v] + cost;
pre[v] = i;
que.emplace(dis[v], v);
}
}
}
return dis[t] != numeric_limits<T>::max();
}
MinCostFlow() {}
MinCostFlow(int n_) {
init(n_);
}
void init(int n_) {
n = n_;
e.clear();
g.assign(n, {});
}
void addEdge(int u, int v, T cap, T cost) {
g[u].push_back(e.size());
e.emplace_back(v, cap, cost);
g[v].push_back(e.size());
e.emplace_back(u, 0, -cost);
}
pair<T, T> flow(int s, int t) {
T flow = 0;
T cost = 0;
h.assign(n, 0);
while (dijkstra(s, t)) {
for (int i = 0; i < n; ++i) {
h[i] += dis[i];
}
T aug = numeric_limits<int>::max();
for (int i = t; i != s; i = e[pre[i] ^ 1].to) {
aug = min(aug, e[pre[i]].cap);
}
for (int i = t; i != s; i = e[pre[i] ^ 1].to) {
e[pre[i]].cap -= aug;
e[pre[i] ^ 1].cap += aug;
}
flow += aug;
cost += aug * h[t];
}
return make_pair(flow, cost);
}
struct Edge {
int from;
int to;
T cap;
T cost;
T flow;
};
vector<Edge> edges() {
vector<Edge> a;
for (int i = 0; i < e.size(); i += 2) {
Edge x;
x.from = e[i + 1].to;
x.to = e[i].to;
x.cap = e[i].cap + e[i + 1].cap;
x.cost = e[i].cost;
x.flow = e[i + 1].cap;
a.push_back(x);
}
return a;
}
};可撤销并查集
struct DSU {
vector<int> f, siz;
vector<array<int, 2>> his;
DSU() {}
DSU(int n) {
init(n);
}
void init(int n) {
f.resize(n + 1);
iota(f.begin(), f.end(), 0);
siz.assign(n + 1, 1);
his.clear();
}
int find(int x) {
while (f[x] != x) {
x = f[x];
}
return x;
}
void merge(int x, int y) {
x = find(x), y = find(y);
if (x == y) return;
if (siz[x] < siz[y]) swap(x, y);
his.push_back({x, y});
f[y] = x;
siz[x] += siz[y];
}
int time() {
return his.size();
}
bool same(int x, int y) {
return find(x) == find(y);
}
int size(int x) {
return siz[find(x)];
}
void revert(int tm) {
while (his.size() > tm) {
auto [x, y] = his.back();
his.pop_back();
f[y] = y;
siz[x] -= siz[y];
}
}
};线段树
template<class Int>
struct Tag {
Int v = 0;
void operator+=(const Tag<Int> &o) {
v += o.v;
}
bool check() {
return v != 0;
}
};
template<class Int>
struct Info {
Int val = 0;
int l, r;
Info operator+(const Info<Int> &o) const {
Info res;
res.l = l;
res.r = o.r;
res.val = val + o.val;
return res;
}
void operator+=(const Tag<Int> &o) {
val += o.v * (r - l + 1);
}
bool check() {
return l != r;
}
};
template<class Int>
class SegTree {
private:
vector<Info<Int>> info;
vector<Tag<Int>> tag;
int n;
int ls(int x) {return x << 1;}
int rs(int x) {return x << 1 | 1;}
void print(int x, int l, int r) {
cout << x << ":[" << l << "," << r << "],val:" << info[x].val << ",tag:" << tag[x].v << "\n";
if (l == r) return;
int mid = l + r >> 1;
print(ls(x), l, mid);
print(rs(x), mid + 1, r);
}
template<class Array>
void build(int x, int l, int r, Array &data) {
if (l == r) {
info[x].l = l;
info[x].r = r;
info[x].val = data[l];
return;
}
int mid = (l + r) >> 1;
build(ls(x), l, mid, data);
build(rs(x), mid + 1, r, data);
info[x] = info[ls(x)] + info[rs(x)];
}
void push_down(int x) {
if (tag[x].check() && info[x].check()) {
info[ls(x)] += tag[x];
info[rs(x)] += tag[x];
tag[ls(x)] += tag[x];
tag[rs(x)] += tag[x];
tag[x] = {0};
}
}
void update(int x, int l, int r, int lq, int rq, Tag<Int> v) {
if (rq < l || lq > r) return;
if (lq <= l && r <= rq) {
info[x] += v;
tag[x] += v;
return;
}
push_down(x);
int mid = (l + r) >> 1;
update(ls(x), l, mid, lq, rq, v);
update(rs(x), mid + 1, r, lq, rq, v);
info[x] = info[ls(x)] + info[rs(x)];
}
void modify(int x, int l, int r, int pos, Int v) {
if (r < pos || l > pos) return;
if (l == r && l == pos) {
info[x].val = v;
return;
}
int mid = (l + r) >> 1;
modify(ls(x), l, mid, pos, v);
modify(rs(x), mid + 1, r, pos, v);
info[x] = info[ls(x)] + info[rs(x)];
}
Info<Int> ask(int x, int l, int r, int lq, int rq) {
if (rq < l || lq > r) return {Info<Int>()};
if (lq <= l && r <= rq) return info[x];
push_down(x);
int mid = (l + r) >> 1;
auto ans = ask(ls(x), l, mid, lq, rq) + ask(rs(x), mid + 1, r, lq, rq);
return ans;
}
public:
SegTree(int n_): n(n_), info(4 * n_ + 1), tag(4 * n_ + 1) {}
void print() {
print(1, 1, n);
}
template<class Array>
void build(Array &data) {
build(1, 1, n, data);
}
void update(int l, int r, Tag<Int> v) {
update(1, 1, n, l, r, v);
}
void modify(int pos, Int v) {
modify(1, 1, n, pos, v);
}
Info<Int> ask(int l, int r) {
return ask(1, 1, n, l, r);
}
};Complex3
// x^3 = 1, x != 1
template<class Int>
struct Complex3 {
Int a, b;
Complex3(Int a = Int(), Int b = Int()) : a(a), b(b) {}
Complex3 operator+(const Complex3& rhs) const {
return Complex3<Int>(a + rhs.a, b + rhs.b);
}
Complex3 operator-(const Complex3& rhs) const {
return Complex3<Int>(a - rhs.a, b - rhs.b);
}
Complex3 operator*(const Complex3& rhs) const {
Int ac = a * rhs.a;
Int bd = b * rhs.b;
Int ad = a * rhs.b;
Int bc = b * rhs.a;
return Complex3<Int>(ac - bd, ad + bc - bd);
}
Complex3 operator/(const Complex3& rhs) const {
return (*this) * rhs.inv();
}
Complex3 inv() const {
Int norm = a * a - a * b + b * b;
return Complex3<Int>((a - b) / norm, - b / norm);
}
Complex3& operator+=(const Complex3& rhs) {
*this = (*this) + rhs;
return *this;
}
Complex3& operator-=(const Complex3& rhs) {
*this = (*this) - rhs;
return *this;
}
Complex3& operator*=(const Complex3& rhs) {
*this = (*this) * rhs;
return *this;
}
Complex3& operator/=(const Complex3& rhs) {
*this = (*this) / rhs;
return *this;
}
bool isZero() const {
return a == 0 && b == 0;
}
};矩阵
template<class Int>
struct Matrix {
int n, m;
vector<vector<Int>> a;
Matrix(int n = 0, int m = 0, Int val = Int())
: n(n), m(m), a(n, vector<Int>(m, val)) {}
static Matrix identity(int n) {
Matrix I(n, n);
for (int i = 0; i < n; i++)
I.a[i][i] = Int(1);
return I;
}
vector<Int>& operator[](int i) {
return a[i];
}
const vector<Int>& operator[](int i) const {
return a[i];
}
Matrix operator + (const Matrix& other) const {
assert(n == other.n && m == other.m);
Matrix res(n, m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
res[i][j] = a[i][j] + other[i][j];
return res;
}
Matrix operator - (const Matrix& other) const {
assert(n == other.n && m == other.m);
Matrix res(n, m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
res[i][j] = a[i][j] - other[i][j];
return res;
}
Matrix operator*(const Matrix& other) const {
assert(m == other.n);
Matrix res(n, other.m, Int(0));
for (int i = 0; i < n; i++)
for (int k = 0; k < m; k++)
for (int j = 0; j < other.m; j++)
res[i][j] = res[i][j] + a[i][k] * other[k][j];
return res;
}
Matrix operator*(const Int& k) const {
Matrix res(n, m);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
res[i][j] = a[i][j] * k;
return res;
}
Matrix transpose() const {
Matrix res(m, n);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
res[j][i] = a[i][j];
return res;
}
Matrix ksm(ll exp) const {
assert(n == m);
Matrix base = *this;
Matrix res = identity(n);
while (exp > 0) {
if (exp & 1) res = res * base;
base = base * base;
exp >>= 1;
}
return res;
}
};
template<class T>
T determinant(int n, Matrix<T>& mat) {
T det(1, 0);
int sign = 1;
for (int i = 0; i < n; i++) {
int pivot = i;
while (pivot < n && mat[pivot][i].isZero()) pivot++;
if (pivot == n) return T();
if (pivot != i) {
swap(mat[i], mat[pivot]);
sign = -sign;
}
det *= mat[i][i];
for (int j = i + 1; j < n; j++) {
if (!mat[j][i].isZero()) {
T factor = mat[j][i] / mat[i][i];
for (int k = i; k < n; k++) {
mat[j][k] -= factor * mat[i][k];
}
}
}
}
if (sign == -1) {
det = T() - det;
}
return det;
}