练习赛 Round 147 题解

https://anoth3r.top/practice147/

A 小月的前缀（构造version）

题目要求 的得分严格最大。

我们可以尝试一种极端的构造策略：让 的得分为 ，而让其他所有 () 的得分都为 ​ 。

时间复杂度：

评分：

void solve() {
	int n, r;
	cin >> n >> r;
	for (int i = 1; i <= n; ++i) cout << (i == r + 1 ? 1 : -1000000000) << " ";
	cout << "\n";
}

B 小月的排序

任意正整数 都可以唯一分解为 ，其中 是不含平方因子的整数（即 的质因数分解中所有质数的指数都为 1），我们称 为 的无平方因子部分，记作 。

两数乘积为：

要使 是完全平方数，必须满足 是完全平方数。由于 和 都不含平方因子，唯一的可能是 。 这意味着，数组中的元素被分成了若干个部分。同一个部分内的数字可以任意交换位置，但不同部分的数字无法交换位置。

原数组 在位置 上的数 ，如果想要移动到它在有序数组中的正确位置，或者说，有序数组 在位置 上的数 想要能够来到这个位置，它们必须属于同一个部分。

换句话说，对于每一个位置 ，原数组该位置的数 必须和排序后该位置的数 能够发生交换。

即：对于所有 ，必须满足 ，等价于判断 ​ 是否为完全平方数。

时间复杂度：

评分：

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 小月的计数

• 左半部分：对于所有的 ，计算 的值。我们可以统计每一个余数 在左边出现的次数，记为 。
• 右半部分：对于所有的 ，计算 的值。同样统计每一个余数 在右边出现的次数，记为 。

那么根据乘法原理，使得等式两边都等于 的 组合共有 ​ 对。

时间复杂度：

评分：

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 小月的前缀

原数组的前缀和数组为 ，即 。

为了方便处理循环移位，我们将原数组复制一份接在后面，形成长度为 的数组。记在这个扩展数组上的前缀和为 。

即 表示扩展数组前 个元素的和。

对于偏移量 ，移位后的数组实际上对应扩展数组中下标从 开始、长度为 的子段。

移位后数组的第 个前缀和可以表示为：

前缀和 的数量，即满足：

其中 。

对于每一个偏移量 ，我们需要在滑动窗口 中，统计有多少个元素严格大于基准值 ​ 。

由于数组下标较大，所以需要离散化。

时间复杂度：

评分：

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 小月的交换

交换相邻边的标记，实际上相当于让标记 在图的边上移动。

• 例如，边 有 ，边 有 。交换后， 从 移动到了 。这一步操作经过了公共顶点 ，花费代价为 。

操作只是移动 ，不会产生或消失 。因此，若 中 的数量与 中不同，直接输出 。

我们需要将所有“多余的 ”（即 的边）移动到“缺少的 ”（即 的边）的位置上。

这就变成了一个 二分图最小权匹配 或 最小费用最大流 问题。

需要注意的是，从一条边 移动到相邻边 （假设它们在原图中通过顶点 相连），路径是： 。

此时的费用为 ，但是实际一次交换代价为 ，所以记得除以 ​ 。

时间复杂度：

评分：

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 小月的色图

不同颜色的边互不干扰。我们可以分别处理每一种颜色，判断该颜色在哪些时间段内是二分图，哪些时间段内不是。

我们可以建立一个全局的数据结构，初始时认为所有 种颜色在所有时间点都是二分图（值为 ）。当我们检测到某种颜色 在时间段 内不是二分图时，我们将该时间段的答案减 ​ 。

对于动态的“插入/删除”操作，我们可以将其转化为“边存在的时间区间”。

• 例如，一条边在第 次操作被插入，第 次操作被删除，则它存在于时间区间 。
• 这样，问题就变成了：给定若干个带有时间区间的边，判断每个时刻图是否为二分图。

对于这种“允许离线、支持边的删除”的动态图问题，我们采用线段树分治。

我们对操作的时间轴 建树。树上的每个节点代表一个时间区间 。

将每一条边（根据其存在的时间区间）挂载到时间线段树的对应节点上。如果一条边存在于 ，它会被挂载到覆盖 的 个线段树节点上。

从根节点开始遍历整棵树：

1. 进入节点：将挂载在该节点上的所有边加入图（使用并查集 ）。
2. 判定与剪枝：检查当前颜色是否出现了奇环（二分图判定条件）。
   • 如果出现奇环，说明在该节点覆盖的整个时间区间 内，该颜色都不是二分图。
   • 直接在全局答案线段树上对 区间减 1。
   • 剪枝：既然已经有奇环，添加更多边也不可能消除奇环，因此不需要继续递归子节点，直接返回。
3. 递归：如果当前没有奇环，且 ，则递归处理左右子节点。
4. 回溯：离开节点时，将步骤 1 中加入的边从 ​ 中撤销，恢复现场。

奇环判定：

• 将每个点 拆成两个点 和 。
• 连边 时，合并 和 。
• 如果 和 在同一个集合中，说明存在奇环，图不是二分图。

时间复杂度：

评分：

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 小月的炼金术

求生成树权值之和，我们很容易想到使用矩阵树定理：图的生成树权值之和等于其基尔霍夫矩阵（即度数矩阵减去邻接矩阵）的任意一个 主子式的行列式。

标准的矩阵树定理计算的是所有生成树的权值和，无法直接过滤出满足特定计数条件的生成树。

这里的约束条件涉及 。处理模 的计数问题，常用的技巧是单位根反演。

我们可以给每条边赋予一个额外的多项式变量 的指数：

• 火元素：贡献 ，对应权值 。
• 冰元素：贡献 ，对应权值 。
• 普通元素：贡献 ，对应权值 。

如果我们能计算出多项式 ，那么我们要求的答案就是 中 的指数为 的项的系数之和。

利用 次单位根 的性质： 。

我们只需要分别计算 时代入基尔霍夫矩阵求出的行列式值 ，然后计算：

由于是在模 下进行运算，我们需要处理复数 。

定义 满足 ，即 。

我们可以定义一种类似于复数的结构 ，形如 ，其中 为模 下的整数。

• 加法：

• 乘法：利用 展开。

  。

• 除法（求逆）：需要计算模长：​ 。

时间复杂度：

评分：

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;
}