DDJ Regular Contest Round#6 Tutorial

DDJ Regular Contest Round#6 Tutorial

a624 A. Benson 的數學課

可以從前幾項來推測答案是

\frac{x \cdot (x - 1)}{2}

，接著嚴謹證明如下:
step 1.
若

n = 1

，得分為

0 = \frac{1 \cdot (1 - 1)}{2} = 0

，命題成立。
step 2.
設

n = k

時，根據歸納假設將

k

拆成任意

a, b

滿足

a + b = k

且

a, b \in N

，由於

a, b < k

，所以可從歸納法得到兩項最後分別會是

\frac{a^{2} - a}{2}, \frac{b^{2} - b}{2}

分，以及現在得到的

a \times b

分，加起來

\frac{a^{2} - a}{2} + \frac{b^{2} - b}{2} + a b = \frac{a^{2} + b^{2} - 2 a b - a - b}{2} = \frac{k^{2} - k}{2}

，因此式子成立，得證。









#include <bits/stdc++.h>
using namespace std;
int main() {
	int T; cin >> T;
	while (T--) {
		int x;
		cin >> x, cout << 1LL * x * (x - 1) / 2 << '\n';
	}
}

a630 B. Benson 的體育課

可以發現答案有以下關係式:

f (N) = {\begin{cases} 0 & , N \equiv 1 (\mod 2) \\ 4 f (N - 2) - f (N - 4) & , N \geq 6 \\ 3 & , N = 2 \\ 11 & , N = 4 \end{cases}

這有證明
https://math.stackexchange.com/questions/2392795/domino-tiling-on-a-3-by-n-rectangle

由於

1 \leq N \leq 10^{18}

，可用矩陣快速冪優化做到複雜度在

O (2^{3} \log N)

的時間完成。
由於方便且再優化常數可以先判斷奇偶，只對偶數做矩陣快速冪。

[\begin{matrix} 4 & - 1 \\ 1 & 0 \end{matrix}] [\begin{matrix} f (N - 1) \\ f (N - 2) \end{matrix}] = [\begin{matrix} f (N) \\ f (N - 1) \end{matrix}]































#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int mod = 998244353;
template <typename T> using vec = vector<T>;
template <typename T> using matrix = vec<vec<T>>;
template <typename T>
matrix<T> operator*(const matrix<T>& a, const matrix<T>& b) {
	int n = a.size(), r = b.size(), m = b.front().size();
	matrix<T> ret(n, vec<T>(m));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < m; j++)
			for (int k = 0; k < r; k++)
				ret[i][j] = (ret[i][j] + a[i][k] * b[k][j] + mod) % mod;
	return ret;
}
int fpow(ll n) {
	matrix<ll> ret{{11}, {3}}, t{{4, -1}, {1, 0}};
	for (; n; n >>= 1, t = t * t)
		if (n & 1) ret = t * ret;
	return ret[1][0];
}
int main() {
	int T; cin >> T;
	while (T--) {
		ll n; cin >> n;
		if (n & 1) cout << "0\n";
		else cout << fpow(n / 2 - 1) << '\n';
	}
}

a631 C. Benson 的福利社

其實就是求序列的中位數而已，如果

N

是偶數，則

[a r r [m i d], a r r [m i d + 1]]

的整數都是答案。

這有證明
https://math.stackexchange.com/questions/113270/the-median-minimizes-the-sum-of-absolute-deviations-the-ell-1-norm









#include <bits/stdc++.h>
using namespace std;

int main() {
	int n; cin >> n;
	vector<int> v(n);
	for (auto& i : v) cin >> i;
	cout << v[n / 2] << '\n';
}

a632 D. Benson 的美術課

帶修改莫隊經典問題，時間複雜度為

O (N^{\frac{5}{3}})

。
後來發現沒有卡好數字範圍，可以用 bitset 唬爛過去 QQ。

程式碼代補























// 唬爛做法
void solve() {
	int n, q; cin >> n >> q;
	int a[n + 1];
	bitset<1000001> b;
	for (int i = 1; i <= n; i++) cin >> a[i];
	while (q--) {
		bool op; cin >> op;
		if (op) {
			int l, r, ans = 0; cin >> l >> r;
			b.reset();
			for (int i = l; i <= r; i++) {
				if (!b[a[i]]) ans++;
				b[a[i]] = 1;
			}
			cout << ans << '\n';
		}
		else {
			int x, v; cin >> x >> v;
			a[x] = v;
		}
	}
}

a516 E. Benson 的 LCM

線段樹裸題，不過因為數字範圍頗大，需要使用動態開點再帶上懶標記，如果一個區間只有一個數字的話，就標記它，該區間不再往下遞迴建構，以此類推，下次經過時再下放一層。
































































#pragma GCC optimize("O2")
#include <bits/stdc++.h>
using namespace std;
#define gcd __gcd // C++17 up
using ll = long long;

ll N; // max of row size
struct node {
	node *l, *r; ll v, tag;
	void pull() {
		ll g = gcd(l ? l->v : 1LL, r ? r->v : 1LL);
		v = (l ? l->v : 1LL) * (r ? r->v : 1LL) / g;
	}
	void push(ll l, ll r) {
		ll m = (l + r) >> 1;
		if (tag <= m) this->l = new node(v, tag);
		else this->r = new node(v, tag);
		tag = -2;
	}
	node(ll _v = 1, ll _tag = -1): v(_v), tag(_tag) {
		l = r = nullptr;
	}
} *root = nullptr;
void upd(node*& o, ll x, ll v, ll l = 1LL, ll r = N) {
	if (!o) o = new node;
	if (o->tag == x || l == r) {
		o->v = v;
		return;
	}
	if (o->tag == -1) {
		o->tag = x, o->v = v;
		return;
	}
	if (o->tag > 0) o->push(l, r);
	ll m = (l + r) >> 1;
	if (x <= m) upd(o->l, x, v, l, m);
	else upd(o->r, x, v, m + 1, r);
	o->pull();
}
ll qry(node* o, ll ql, ll qr, ll l = 1LL, ll r = N) {
	if (!o) return 1;
	if (ql <= l && r <= qr) return o->v;
	if (o->tag > 0) return ql <= o->tag && o->tag <= qr ? o->v : 1;
	ll m = (l + r) >> 1, lret = 0, rret = 0;
	if (ql <= m) lret = qry(o->l, ql, qr, l, m);
	if (qr > m) rret = qry(o->r, ql, qr, m + 1, r);
	ll g = gcd(lret ? lret : 1LL, rret ? rret : 1LL);
	return (lret ? : 1LL) * (rret ? : 1LL) / g;
}
int main() {
	ios::sync_with_stdio(false), cin.tie(nullptr);
	int Q; cin >> N >> Q;
	while (Q--) {
		int op; cin >> op;
		if (op == 1) {
			ll x, v; cin >> x >> v;
			upd(root, x, v);
		}
		else {
			ll ql, qr; cin >> ql >> qr;
			cout << qry(root, ql, qr) << '\n';
		}
	}
}