<center> <h1> week of 1/8 </h1>

</center>

---
### `📝 notes`

\>:[

---

## magic five

a truly magical number.

### problem
you're given a long number consisting of $n$ digits repeating $k$ times.

Iahub wants to delete some digits (possibly none, but not all) such that he gets a magic number, or a number on the table is divisible by $5$.

Count the number of ways he can delete digits. modulo $10^9 + 7$. Two ways are different if the set of digits that you delete is different.

$$n \leq 10^5, k \leq 10^9$$
### solution

first ill explain how input works, because it might be confusing.

if we're given the string "1234", $n=4$, and $k=3$, then the number on the plate is:

$$123412341234$$

or $1234$ repeated $k=3$ times.

note that the length of the ending string can be up to $10^{14}$ in length, so we can't iterate through this string.

---

first, a number divisible by $5$ if and only if it ends with a $0$ or $5$.

with this in mind, let's first figure out the case where $k=1$.

then as we iterate through the string, if $s_i = 0$ or $s_i = 5$, then we can end with this digit, deleting any combination of the previous digits, or $2^i$.

our answer is simply the sum of this.

however, we can't just iterate through this sequence.

in a larger example, for each $i$, we'd add $2^i + 2^{i+n} + 2^{i + 2n} + \dots + 2^{i + kn}$.

we can split this into: $(2^i * k) * (2^0 + 2^{n} + 2^{2n} + \dots + 2^{kn})$

now, we just have to compute the right side, since any $2^i$ can be computed with binary exponentation in $\mathcal{O}(\log n)$.

if you think about it for a second, the right side is a geometric series!

each time, the term is multiplied by $2^n$.

we can solve this with the standard sum geometric sequence formula:

$$S_n = \frac{(1 - 2^{nk})}{1-2^n}$$

note that since we have to perform division under mod, we'll have to calculate the modular inverse with Fermat's Little Theorem.

there are a couple more caveats when coding up binary exponentation and division underneath $10^9 + 7$ (a prime), but you can read about it here: [cp-algo link](https://cp-algorithms.com/algebra/binary-exp.html).

something a little extra about calculating exponents.

By FLT: $a^{p-1} \equiv 1 \pmod p$, for any prime,
so we can use calculate $a^{k \mod (p-1)}$ instead.

oh, and if you wanted to watch a video, Errichto has a really good one on it: {%youtube L-Wzglnm4dM %}

---

## implementation:

// oh, these hills, they burn so bright, oh, these hills, they bring me life
#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
#define endl "\n"
#define f first
#define s second
#define pi pair<int, int>
#ifdef __INTELLISENSE__
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#endif
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#else
#define dbg(...) 0
#endif

const int MOD = 1e9 + 7;
template <ll M>
struct modint {
	// bin exp, use binary to calculate powers -- in o(log n) instead
	// sprinkle in a little FLT to calculate via prime mods
	// a^(n-1) = 1 mod n, so rewrite original n^k as n^(\lfloor k/(n-1) \rfloor) * n^(k%(n-1)), reduce left side to 1, and we have the same equation
	static ll _pow(ll n, ll k) {
		ll r = 1;
		for (; k > 0; k >>= 1, n = (n * n) % M)
			if (k & 1) r = (r * n) % M;
		return r;
	}

	ll v;
	modint(ll n = 0) : v(n % M) { v += (M & (0 - (v < 0))); }

	friend string to_string(const modint n) { return to_string(n.v); }
	friend istream& operator>>(istream& i, modint& n) { return i >> n.v; }
	friend ostream& operator<<(ostream& o, const modint n) { return o << n.v; }
	template <typename T>
	explicit operator T() { return T(v); }

	friend bool operator==(const modint n, const modint m) { return n.v == m.v; }
	friend bool operator!=(const modint n, const modint m) { return n.v != m.v; }
	friend bool operator<(const modint n, const modint m) { return n.v < m.v; }
	friend bool operator<=(const modint n, const modint m) { return n.v <= m.v; }
	friend bool operator>(const modint n, const modint m) { return n.v > m.v; }
	friend bool operator>=(const modint n, const modint m) { return n.v >= m.v; }

	modint& operator+=(const modint n) {
		v += n.v;
		v -= (M & (0 - (v >= M)));
		return *this;
	}
	modint& operator-=(const modint n) {
		v -= n.v;
		v += (M & (0 - (v < 0)));
		return *this;
	}
	modint& operator*=(const modint n) {
		v = (v * n.v) % M;
		return *this;
	}
	modint& operator/=(const modint n) {
		v = (v * _pow(n.v, M - 2)) % M;
		return *this;
	}
	friend modint operator+(const modint n, const modint m) { return modint(n) += m; }
	friend modint operator-(const modint n, const modint m) { return modint(n) -= m; }
	friend modint operator*(const modint n, const modint m) { return modint(n) *= m; }
	friend modint operator/(const modint n, const modint m) { return modint(n) /= m; }
	modint& operator++() { return *this += 1; }
	modint& operator--() { return *this -= 1; }
	modint operator++(int) {
		modint t = *this;
		return *this += 1, t;
	}
	modint operator--(int) {
		modint t = *this;
		return *this -= 1, t;
	}
	modint operator+() { return *this; }
	modint operator-() { return modint(0) -= *this; }

	modint pow(const ll k) const {
		return k < 0 ? _pow(v, M - 1 - (-k % (M - 1))) : _pow(v, k);
	}
	modint inv() const { return _pow(v, M - 2); }
};

using mi = modint<int(MOD)>;
#define int ll

/*
 * =notes=
 * 1) sum of all chooses is 2^n
 * 2) if we have some 0 or 5 in the middle, if we want to "end" with it, remove everything to the right
 * 3) god damn i wanna be able to iterate through k, but seems like it won't happen. let's figure out a
 * 		better way to calc powers
 *
 * 4) the largest addition is gonna be 2^(s * k - (num elements behind rightmost 5/0)) -- compute with flt & bin exp
 * 5) the largest addition is gonna be 2^(s * k - (num elements behind rightmost 5/0)) -- compute with flt & bin exp
 *
 *
 * yo, so for each i, we have 2^i-1 contribution
 * so... 2^(i - 1) + 2^(i + n - 1) + 2^(i + 2n - 1) ...
 *
 * 2^(i- 1) * n * (2^(0) + 2^(n) + 2^(2n))
 *
 * wow look it's a geometric sequence! r = 2^n -> r^k = 2^(n*k)
 * this delta (standard sum geo) = (1- 2^(n*k)) / (1-2^n)
 */
signed main() {
	cin.tie(0)->sync_with_stdio(0);

	string s;
	cin >> s;
	int k;
	cin >> k;
	int n = sz(s);

	mi num = (mi(1) - num._pow(2, n * k));
	mi den = (mi(1) - num._pow(2, n));

	num /= den;

	mi ans = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == '0' || s[i] == '5') {
			// yay we got 2^i (zero-indexed)
			ans += ans._pow(2, i);
		}
	}

	ans *= num;
	cout << ans.v << endl;
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o

##

## Cereal 2

linky: [http://www.usaco.org/index.php?page=viewproblem2&cpid=1184](http://www.usaco.org/index.php?page=viewproblem2&cpid=1184).

### problem

In this problem, we're given a list of $n$ cows, who like cereal, so much, that they'll eat an entire box for breakfast.

Each cow has a favorite cereal and a second favorite cereal, all of these cereals are numbered from $1 \dots m$.

The cows line up, and in order, they each take one box of cereal. If their favorite cereal is available, then they'll take it, otherwise, if their second favorite cereal is available, they'll take that, otherwise, they'll moo in disappointment.

Farmer John has ordered $M$ boxes of cereal, numbered $1 \dots M$, find the ordering which minimizes the number the cows that will moo in disappointmnet, and output a permutation, of the cow's order, which satisfies the minimum disappointment.

### solution

a a a a a a a a a a a a a a a a a aaa aa a a a

this problem is kinda hard >.<

however, note that if we form a directed edge from each cow's favorite cereal, to second favorite cereal, we can solve each connected component independently.

let $E$ represent the number of edges in the connected component (cows), and $V$ represent the number of vertices in the connected component (cereal).

then, we only have a few caes:

$V = E - 1$:
We have a tree! We can give all $E - 1$ cereal by going through the connected component in DFS order.

$V = E$:
We have a tree, with an extra edge. Let's find the cycle in this graph, and remove an edge and one vertex from this cycle. Then, we can proceed and solve it as a tree.

$E > V$:
Our general formula is that we cannot satisfy $\max(0, E - V)$.

We'll follow the same thing as the last case, removing one edge on the cycle, and then, going through the DFS Tree, unfortunately, ignoring all the edges that we miss.

The edges that we don't pass will just be tossed to the end of the permutation.

That should be it, as we iterate through the components in linear time.

---

since my implementation is stored locally on my computer..., ill give you the official solution by USACO!

#include <bits/stdc++.h>
 
using namespace std;
 
struct edge {
    int cow; // which cow's choice 
    int to;
    bool is_first;
 
    edge() {};
    edge(int cow, int to, bool is_first) : cow(cow), to(to), is_first(is_first) {};
};
 
int N, M;
 
vector<edge> adj[100001];
bool visited_cycle[100001]; // array for cycle finding
bool visited[100001]; // visited array for finding which order of cows we should use
bool gets_cereal[100001]; 
 
int hungry_cows = 0;
queue<int> order;
int ignore_edge = -1;
int first_cereal = -1; // the cereal we start the search from, if the CC is not a tree then this must be on a cycle
 
void find_cycle(int cur, int prev = -1) {
    visited_cycle[cur] = true; 
 
    for (edge next : adj[cur]) {
        if (visited_cycle[next.to]) {
            if (first_cereal == -1 && next.to != prev) {
                if (next.is_first) {
                    first_cereal = next.to; 
                } else {
                    first_cereal = cur;
                }
                
                ignore_edge = next.cow; 
                order.push(next.cow);
                gets_cereal[next.cow] = true;
            }
        } else {
            find_cycle(next.to, cur);
        }
    }
}
 
 
void dfs(int cur) {
    visited[cur] = true;
    for (edge next : adj[cur]) {
        if (!visited[next.to] && next.cow != ignore_edge) { 
            gets_cereal[next.cow] = true;
            order.push(next.cow);
            dfs(next.to);
        }
    }
}
 
 
int main() {
    cin >> N >> M;
    for (int i = 0; i < N; ++i) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(edge(i+1, b, false));
        adj[b].push_back(edge(i+1, a, true));
    }
 
    for (int i = 1; i <= M; ++i) {
        first_cereal = -1;
        ignore_edge = -1;
        if (!visited[i]) {
            find_cycle(i);
           
            if (first_cereal > 0) {
                dfs(first_cereal);
            } else {
                dfs(i);
            }
        }
    }
 
    for (int i = 1; i <= N; ++i) {
        if (!gets_cereal[i]) {
            ++hungry_cows;
            order.push(i);
        } 
    }
 
    cout << hungry_cows << endl;
    while (!order.empty()) {
        cout << order.front() << endl; 
        order.pop();
    }
 
    return 0;
}

## interesting sequence

link: [https://codeforces.cc/contest/1775/problem/C](https://codeforces.cc/contest/1775/problem/C)

### problem
we are given an integer $n$ and $x$, and we have to find the minimum $m$ such that, $n \& (n+1)\& \dots (m) = x$. if it's not possible, print $-1$.

here, $\&$ represents the [bitwise AND operator](https://en.wikipedia.org/wiki/Bitwise_operation#AND).

---

### solution

the idea is that $\&$ is a decreasing operator, since we can't gain any bit we don't have, thus, $x \leq n$. (also $n \& x = x$, but not strictly needed).

this leads us to binary search on the answer. we can get the bitwise AND of a range in $\mathcal{O}(\log_2 n)$ by finding the longest common prefix, and zeroing out the rest.

if no such $m$ reaches $x$, then there is no answer.

time complexity is $\mathcal{O}(log_n \times log_n = \log^2_n)$

--

implementation:

// oh, these hills, they burn so bright / oh, these hills, they bring me life
#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
#define endl "\n"
#define f first
#define s second
#define pi pair<int, int>
#ifdef __INTELLISENSE__
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#endif
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#else
#define dbg(...) 0
#endif

ll rng(ll a, ll b) {
	ll sht = 0;
	while (a != b) {
		a >>= 1;
		b >>= 1;
		sht++;
	}
	return (a << sht);
}
void solve() {
	ll x, y;
	cin >> x >> y;
	if (y > x) {
		cout << -1 << endl;
		return;
	}

	ll lo = x, hi = 5 * 1e18;
	bool uwu = 0;
	while (lo < hi) {
		ll mid = lo + (hi - lo) / 2;
		if (rng(x, mid) <= y) {
			if (rng(x, mid) == y) {
				uwu = 1;
			}
			hi = mid;
		} else {
			lo = mid + 1;
		}
	}
	cout << (uwu ? lo : -1) << endl;
}

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

	int tc;
	cin >> tc;

	for (int _ = 0; _ < tc; _++) {
		solve();
#ifdef LOCAL
		cout << "____________________" << endl;
#endif
	}
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o

---

## Friendly Spiders

link: [https://codeforces.cc/contest/1775/problem/D](https://codeforces.cc/contest/1775/problem/D)

### problem

we have $n \leq 3 * 10^5$ binary spiders, each having a different number of legs, up to $3 \times 10^5$. spiders which share a GCD greater than $1$, can send a message to each other in one second.

or, if ($\gcd(a_i, a_j)$ > 1), then spider $i$ and $j$ can talk.

we're given two spiders $s, t$ and we have to see if they can communicate, and if so, find the minimum time and output a viable path.

---

### solution

the idea is that we can link each spider to each of it's prime divisors, which are guaranteed to be less than $\sqrt{n}$ if you remember from earlier in the year.

thus, we can link each spider to each of it's prime divisors and do a Breadth First Search (with Dijkstra's Algorithm).

we'll get the distance as $\lfloor \frac{\texttt{dist}[t]}{2} \rfloor + 1$, and we'll backtrack to find the path with a parent array.

// oh, these hills, they burn so bright / oh, these hills, they bring me life
#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
#define endl "\n"
#define f first
#define s second
#define pi pair<int, int>
#ifdef __INTELLISENSE__
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#endif
#ifdef LOCAL
#include "/mnt/c/yukon/dbg.cpp"
#include "/mnt/c/yukon/pp.hpp"
#else
#define dbg(...) 0
#endif

const int uwu = 4 * 1e5;
int main() {
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin >> n;
	vector<int> a(n);
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	vector<vector<int>> adj(uwu * 2);

	// map from num -> prime, prime -> num
	for (int i = 0; i < n; i++) {
		// pray for no tle
		int cur = a[i];
		for (int j = 2; j * j <= a[i]; j++) {
			if (cur % j == 0) {
				adj[i].push_back(uwu + j);
				adj[uwu + j].push_back(i);
			}
			while (cur % j == 0) {
				cur /= j;
			}
		}
		if (cur > 1) {
			adj[i].push_back(uwu + cur);
			adj[uwu + cur].push_back(i);
		}
	}

	int s, t;
	cin >> s >> t;
	--s;
	--t;

	vector<int> dst(uwu * 2, inf);
	vector<int> par(uwu * 2, -1);
	// {i, dist}
	queue<pi> todo;
	todo.push({s, 0});
	dst[s] = 0;

	while (!todo.empty()) {
		pi v = todo.front();
		todo.pop();

		if (v.s > dst[v.f]) continue;

		for (int x : adj[v.f]) {
			if (v.s + 1 < dst[x]) {
				dst[x] = v.s + 1;
				par[x] = v.f;
				todo.push({x, dst[x]});
			}
		}
	}
	if (dst[t] == inf) {
		cout << -1 << endl;
	} else {
		cout << dst[t] / 2 + 1 << endl;

		vector<int> path;
		int cur = t;
		while (cur != -1) {
			if (cur < uwu) path.push_back(cur);
			dbg(cur);
			cur = par[cur];
		}
		reverse(all(path));
		for (int i = 0; i < sz(path); i++) {
			cout << ++path[i] << ' ';
		}
		cout << endl;
	}
}

// don't get stuck on one approach
// question bounds
// flesh out your approach before implementing o.o

## Clock Tree

i don't have that much time to explain & implement it, so i'll try my best...

### problem
so we have a tree $n \leq 2500$, and we have some clocks at each node, which can be set from integers from $1 \dots 12$, everytime we walk "inside" of the node, we don't increment the node that we start at.

---

### solution

the main (super-obvious) observation is that the only cases where we can set two adjacent nodes to both 12, is if they are equal, or if they are $1 \pmod {12}$ apart (start from the larger node).

the not-so-obvious extension of this, is that we can generalize this to a larger tree. in fact, if we two-color the tree, since every tree is bipartite, we can split up the nodes into two groups!

now, we can just manually check sums and output the sizes of each group.

note: a bipartite tree is a tree in which every adjacent node is a different color

pseudo-code:

function DFS (node, parent, color) -> {
    type[node] = color;
    
    each x -> adjacent-to-node {
        if x not equal to parent {
            call, DFS(x, node, color XOR 1)        
        }
    }
}

note that we can root the tree arbitrarily.