<center> <h1> week of 11/7 </h1>

usaco ;w;
</center>

---
### `📝 notes`
I attended BMT (Berkeley Math Tournament) last weekend with some of my friends. I planned to do a writeup of some of the problems, but apparently we shouldn't discuss problems until ~11/20, so I'll just do it then.

<center>+</center><br>

With USACO season just around the corner, I really need to keep upsolving these problems.

---

## [USACO 2016 Open (Gold)](http://www.usaco.org/index.php?page=open16results)

### [Splitting the Field](http://www.usaco.org/index.php?page=viewproblem2&cpid=645)

#### `problem:`
Farmer John plans to enclose all of his cows with a fence, but due to low milk production last quarter, he decides to save money by building two enclosures instead of just one.

Find the total area saved by using $2$ enclosures instead of one.

You are given $n$ cows' coordinates, $1 \leq n \leq 50,000$, with coordinates from $[1, 10^9]$.

#### `solution`
The key observation is that the only way we make two enclosures is to find a split somewhere along the $x$ or $y$ axes.

Thus, we'll sort the cows two times, once by $x$, once by $y$, and calculate prefix and suffix mins and maxes.

time complexity: $\mathcal{O}(n \log n)$

---

### [Closing the Farm](http://www.usaco.org/index.php?page=viewproblem2&cpid=646)

#### `problem:`
Farmer John is planning to close down his farm, since he's planning to go on a long vacation. His farm can be described as $n$ nodes, connected by $m$ bidirectional roads.

When shutting down the farm, FJ closes barns one at a time.

At every point in time, FJ wants to know whether the barn is still fully connected. The barn may not even be fully connected in the first place.

print $n$ lines, **YES** if the barn is fully connected at the $i$th point in time, or **NO** otherwise.

constraints: $n, m \leq 2 \cdot 10^5$

#### `solution:`

In the silver variant, at each point in time, we could just brute force every point in time, and run a DFS with that point removed.

However, that time complexity is $\mathcal{O}(n^2)$, which is much too slow for $2 \cdot 10^5$.

What if we construct the graph in reverse and keep track of connected components?

Let's analyze the time complexity of this.

To check if two nodes share an edge, we can use a Disjoint Set Union, which supports these operations in $\log n$ time.

There are $m$ edges, which we'll have to unite at most $2m$ times over all $n$ closures.

So, our final time complexity is $\mathcal{O}(n + 2m)$, which can be dropped to $\mathcal{O}(n)$.

### [248](http://www.usaco.org/index.php?page=viewproblem2&cpid=647)

#### `problem:`
Bessie is playing a game on her phone, in which she is given $n$ integers in the range $1\dots40$, and she can merge two adjacent, equal elements $x$, and replace them with **one** $x + 1$. Her goal is to make the largest number at the end (when she can't merge anymore).

constraints: $n \leq 248$

#### `solution:`

We'll use Range DP.

Let $\texttt{dp}[l][r]$ = equal the maximum number that can be constructed with the range $l, r$.

Our base case is $l = r$, in which $dp[l][r] = \texttt{val}_r$.

Then, we can get the answer of $l, r$ by trying to merge $(l, c), (c + 1, r)$, such that $c$ is a constant $l \leq c < r$.

time complexity: $\mathcal{O}(n^3)$

---

## [USACO 2016 Dec (Gold)](http://www.usaco.org/index.php?page=dec16results)

### [Moocast](http://www.usaco.org/index.php?page=viewproblem2&cpid=669)

#### `problem:`
Farmer John has $n$ cows who want to communicate with each other. They can all be represented as points on a 2D grid.

By spending $x$ dollars, they can each buy a walkie talkie which can transmit messages up to $\sqrt{x}$ distance away. Or, the squared distance between two cows must be $\leq x$.

To talk to each other, they don't have to have a direct signal to each of the cows, since they can relay messages in a "telephone" style way. Essentially, for any two cows $u, v$, $u$ must be able to reach a cow that can reach $v$.

constraints: $n \leq 1000$, $x, y \leq 25,000$

#### `solution`
We'll just binary search on $x$. Due to the low bounds on $x$, we can just rebuild the graph in $\mathcal{O}(n^2)$.

Time complexity: $\mathcal{O}(n^2 \log n)$

---

### [Cow Checklist](http://www.usaco.org/index.php?page=viewproblem2&cpid=670)

#### `problem:`
Farmer John is planning to visit all of his cows, all of which are of type Holstein or Guernseys,w hich are all points on a 2D grid.

The Holsteins are numbered $1\dots n$, and the Guernseys are numbered $1\dots m$.

At the end, he'll have a sequence which described how he visited the cows. The Guernseys $1 \dots m$ should be a subsequence in the order, and the Holsteins $1 \dots n$ should also appear as a subsequence in the order.

He also wants to minimize the distance in which he walks. More specifically, if he travels between two cows $i, j$, he'll incur a distance traveled of $D^2$ if $D$ is the distance bewteen $i$ and $j$.
#### `solution:`

At every point, we can either go to the $i + 1$th point or the $j + 1$th point. We'll calculate the minimum using a 2D DP.

Time complexity: $\mathcal{O}(nm)$

### [Lasers & Mirrors](http://www.usaco.org/index.php?page=viewproblem2&cpid=671)

#### `problem:`
Bessie wants to point a laser from her to the barn, but it isn't lined up perfectly! The laser and the barn can both be modeled as positions on a 2D grid.

Luckily she has $n$ mirrors set up on $n$ distinct coordinate points which can direct an vertical laser horizontally, or a horizontal laser vertically.

Find the minimum mirrors needed to bring the laser to the barn.

#### `solution:`

We'll just launch a 0/1 BFS since we should only use a mirror at most once.

Unfortunately, that's about it for the problem...

time complexity: $\mathcal{O}(n)$

---

## [Count GCD](https://codeforces.cc/contest/1750/problem/D)

This problem is (in my opinion) an amazing PIE problem.

It's kinda hard to summarize it, so I'll just include a screenshot of the problem statement.

---

#### `solution:`

So, first of all, the value of $b_0$ must be $a_0$, because $\gcd(b) = b$, and $b$ is the only value that works.

Similarly, by definition, $\gcd(b_1, b_2, \dots, b_i) = a_i$, so $gcd(a_i - 1, a_i) = a_i$. Thus, $a_i - 1$ must have the same prime factors as $a_i$. This gives us these two pieces of information:

- $a_{i-1} \geq a_i$ for all $i > 0$
- $a_{i-1} | a_i$ aka ($a_{i-1} \mod a_i = 0$)

This also gives us some new information! $a$ will only have ~$30$ distinct elements.

Why?

The greatest value it can maintain, given the constraints above and $a_{i-1} \neq a_i$ is $\frac{a_i}{2}$, and $10^9 \approx 2^{30}$.

Alright, now we should do some casework. Note that at the end, we'll multiply possibilities for everything together, since every choice is independent.

- $a_{i-1}=a_i$

- $a_{i-1} = a_{i-1} \cdot k$ of any $k$ will work, such that the value is under $m$, so the possiibilties is simply $\lfloor \frac{m}{a_i} \rfloor$

- $a_{i-1} | a_i$

- first, we'll define $a_i$ in terms of $a_{i-1}$. $a_{i - 1} = a_i * \{\text{prime factors}\}$.
- now, you'll note that we can once again choose all possible multiples of $\lfloor \frac{m}{a_i} \rfloor$, except for any combination of the prime factors (since they'll give us a higher $\gcd$).
- the amount of prime factors cannot be $> 15$, so, we'll generate all subsets.
- we really just want to subtract away $\lfloor \frac{m}{\frac{a_i}{\{prime factors\}}} \rfloor$, but we could subtract, say one prime factor multiple times in subsets of two.
- example: prime factors include $\{2, 3\}$, we remove $2 \cdot 3$ twice.
- this is a classic problem with P.I.E! (principle inclusion-exclusion)
- we'll remove subsets of size 1, add back subsets of size 2, ... (remove odds, add evens)

solution in `c++17`:

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

using ll = long long;
#define all(x) begin(x), end(x)
#define rall(x) x.rbegin(), x.rend()
#define sz(x) (int)(x.size())
#define inf 1000000010
#define linf 0x3f3f3f3f3f3f3f3f
#ifdef LOCAL
#define endl "\n"
#include "/mnt/c/yukon/dbg.cpp"
#else
#define dbg(...) 0
#endif
#define int ll
const ll MOD = 998244353;

struct mi {
	int v;
	explicit operator int() const { return v; }
	mi() { v = 0; }
	mi(long long _v) : v(_v % MOD) { v += (v < 0) * MOD; }
};
mi& operator+=(mi& a, mi b) {
	if ((a.v += b.v) >= MOD) a.v -= MOD;
	return a;
}
mi& operator-=(mi& a, mi b) {
	if ((a.v -= b.v) < 0) a.v += MOD;
	return a;
}
mi operator+(mi a, mi b) { return a += b; }
mi operator-(mi a, mi b) { return a -= b; }
mi operator*(mi a, mi b) { return mi((long long)a.v * b.v); }
mi& operator*=(mi& a, mi b) { return a = a * b; }
mi pow(mi a, long long p) {
	assert(p >= 0);
	return p == 0 ? 1 : pow(a * a, p / 2) * (p & 1 ? a : 1);
}
mi inv(mi a) {
	assert(a.v != 0);
	return pow(a, MOD - 2);
}
mi operator/(mi a, mi b) { return a * inv(b); }

template <typename T>
ostream& operator<<(ostream& os, const vector<T>& v) {
	for (int i = 0; i < sz(v); ++i) {
		os << v[i] << ' ';
	}
	return os;
}

const ll mod = 998244353;

vector<ll> pf(ll x) {
	vector<ll> ret;
	for (int i = 2; i * i <= x; i++) {
		if (x % i == 0) {
			ret.push_back(i);
			while (x % i == 0) x /= i;
		}
	}
	if (x > 1) ret.push_back(x);
	return ret;
}

signed main() {
	cin.tie(0)->sync_with_stdio(0);

	int tc;
	cin >> tc;

	for (int _ = 0; _ < tc; _++) {
		int n, m;
		cin >> n >> m;

		vector<int> a(n);
		for (int i = 0; i < n; i++) {
			cin >> a[i];
		}

		bool ok = 1;
		for (int i = 1; i < n; i++) {
			if (a[i - 1] < a[i] || (a[i - 1] % a[i])) {
				ok = 0;
				break;
			}
		}

		if (!ok) {
			cout << 0 << endl;
			continue;
		}

		mi ans = 1;
		for (int i = 1; i < n; i++) {
			if (a[i - 1] == a[i]) {
				ans = (ans * (m / a[i]));
			} else {
				// a_i = a_{i-1} * {prime factors}

				int rem = a[i - 1] / a[i];
				vector<ll> prime = pf(rem);

				ll pie = 0;
				// classic pie, remove 1s, add 2s, remove 3s, ...
				for (int mask = 0; mask < (1 << sz(prime)); mask++) {
					// candiates, a[i] * [m/a[i]] <= m
					ll imtooprecious = m / a[i];
					int cnt = 0;

					for (int j = 0; j < sz(prime); j++) {
						if (mask & (1 << j)) {
							cnt++;
							imtooprecious /= prime[j];
							imtooprecious %= mod;
						}
					}

					pie = ((cnt % 2 ? -1 : 1) * imtooprecious) % mod + (pie % mod);
					pie %= mod;
				}
				ans = ((ans) * (pie % mod));
			}
		}
		cout << ans.v << endl;

#ifdef LOCAL
		cout << "____________________" << endl;
#endif
	}
}

| Implementation Notes: |
| ----------------------|

- Here, I utilize [BenQ's ModInt](https://github.com/bqi343/USACO/blob/master/Implementations/content/number-theory%20(11.1)/Modular%20Arithmetic/ModInt.h) template to avoid tricky overflow situations.

---
thanks for reading!