The number of updates can be counted as the number of ordered pairs $$$(u, v)$$$ such that when $$$u$$$ is going to be removed, there exists at least one path between $$$u$$$ and $$$v$$$.

If the path between $$$u$$$ and $$$v$$$ is unique in the original graph, we can conclude that pair exists if $$$u$$$ is the first removed node on the path with respect to an order, and $$$\frac{1}{cnt(u, v)}$$$ of all possible orders would meet this condition, where $$$cnt(u, v)$$$ is the number of nodes on the unique path between $$$u$$$ and $$$v$$$ (inclusive).

In other cases, there exist exactly two paths between $$$u$$$ and $$$v$$$ at the beginning, each passing through one part of the only cycle in the graph. Let the number of nodes on these two paths be $$$x$$$, $$$y$$$ respectively, and the number of their common nodes be $$$z$$$. The probability that an order corresponds to this pair is $$$\frac{1}{x} + \frac{1}{y} - \frac{1}{x + y - z}$$$.

Let $$$p_1, p_2, \ldots, p_m$$$ be the nodes on the only cycle in order. Let's for each $$$p_i$$$ ($$$i = 1, 2, \ldots, m$$$) build a rooted tree from $$$p_i$$$ without passing any edges on the cycle.

We can firstly handle the case that the path between $$$u$$$ and $$$v$$$ is unique, which implies $$$u$$$ and $$$v$$$ are in the same rooted tree we have built. In this case, we only need to count the number of paths for each possible length, so we can use Centroid Decomposition with Number-Theoretic Transform to do this in total time complexity $$$\mathcal{O}(n \log^2 n)$$$.

Then we have to handle the case passing through the cycle. We can use Divide and Conquers to calculate the contribution of $$$(u, v)$$$, that is, when we merge information from $$$[L, M]$$$ and $$$[M + 1, R]$$$ into $$$[L, R]$$$, we can count for pairs $$$(u, v)$$$ such that $$$u$$$ is from the union of trees whose roots are $$$p_L, p_{L + 1}, \ldots, p_{M}$$$ and $$$v$$$ is from that for $$$p_{M + 1}, p_{M + 2}, \ldots, p_{R}$$$, and vice versa. This part can be done in time complexity $$$\mathcal{O}(n \log n \log m)$$$.

By the way, it is not difficult to count the number of paths for each possible length if the given graph is a cactus.

Note that $$$X_i \bmod (X_j + 1) = X_i - \left \lfloor \frac{X_i}{X_j + 1} \right \rfloor (X_j + 1)$$$, and the number of pairs $$$\left(X_j, \left \lfloor \frac{X_i}{X_j + 1} \right \rfloor\right)$$$ is $$$\mathcal{O}\left(\sum_{i = 1}^{m}\left(\left \lfloor \frac{m - 1}{i} \right \rfloor + 1\right)\right) = \mathcal{O}(m \log m)$$$. If we can get the number of occurrences in an interval of the sequence for values in $$$[0, m)$$$ and calculate the partial sum, we can get the contribution of all $$$X_i$$$ for each pair $$$(X_j, k)$$$ such that $$$k (X_j + 1) \leq X_i < (k + 1) (X_j + 1)$$$, and solve the problem in time complexity $$$\mathcal{O}(m \log m)$$$.

Applying the pigeonhole principle, there must exist two integers $$$p$$$ and $$$q$$$ such that $$$0 \leq p < q \leq m$$$ and $$$X_p = X_q$$$. Also, for any non-negative integer $$$k$$$, we have $$$X_{p + k} = X_{q + k}$$$, and thus $$$\{X_n\}_{n = p}^{\infty}$$$ is a periodic sequence. We can easily count the number of occurrences for all possible values in $$$[l_1, r_1]$$$ and $$$[l_2, r_2]$$$ respectively in total time complexity $$$\mathcal{O}(m)$$$.

If you are very familiar with quadratic congruences, you will know that, under the given data range, the number of candidate positions for the answer in a period of the $$$P$$$-Fibonacci sequence in modulo $$$10^k$$$ is relatively small, like $$$8$$$, and positions for $$$10^k$$$ are easy to obtain from positions for $$$10^{k - 1}$$$. Together with a series of rough analyses, you can write a Breath-First Search to find the answer.

Let's solve the problem step by step. First, we can prove that $$$\{(F_{k + 1}, F_k)\}_{k = 0}^{\infty}$$$ is a pure periodic sequence in modulo any integer $$$m$$$, as we can build an invertible matrix $$$A = \begin{bmatrix} 0 & 1 \\ 1 & P \end{bmatrix}$$$ such that $$$A^k = \begin{bmatrix} F_{k — 1} & F_k \\ F_k & F_{k + 1} \end{bmatrix}$$$.

Let $$$L(m)$$$ be the period length of the $$$P$$$-Fibonacci sequence in modulo $$$m$$$, which means $$$F_i \equiv F_{i + L(m)} \pmod{m}$$$ for any position $$$i$$$. We can try to find all possible $$$x$$$ such that $$$0 \leq x < L(10^k)$$$ and $$$F_x \equiv F_{F_n} \pmod{10^k}$$$, and then for each $$$x$$$, find all possible $$$y$$$ such that $$$0 \leq y < L(L(10^k))$$$ and $$$y \equiv F_x \pmod{L(10^k)}$$$. The answer $$$n$$$ must be in the form of $$$(y + t \cdot L(L(10^k))$$$, so we can find the smallest integer $$$t$$$ for each $$$y$$$ such that $$$n \geq m$$$, and when $$$(F_{F_n} \bmod 10^k)$$$ has leading zeros ($$$k > 1$$$), $$$F_{F_n} \geq 10^k$$$.

Before that, we have to precalculate $$$L(10^k)$$$ and $$$L(L(10^k))$$$ first. In number theory, we know that

• $$$L({p_1}^{e_1} {p_2}^{e_2} \ldots {p_t}^{e_t}) = \mathrm{lcm}(L({p_1}^{e_1}), L({p_2}^{e_2}), \ldots, L({p_t}^{e_t}))$$$, e.g. $$$L(10^k) = \mathrm{lcm}(L(2^k), L(5^k))$$$;
• $$$p^{e - 1} L(p) | L(p^e)$$$ for any prime $$$p$$$ and any positive integer $$$e$$$, e.g. $$$2^{k - 1} L(2) | L(2^k)$$$;

By enumerating different possible $$$P$$$, we can get $$$L(2) \in \{2, 3\}$$$, $$$L(5) \in \{12, 20\}$$$, so $$$\frac{L(10^k)}{10^{k - 1}} \in \{3, 6, 10, 15\}$$$ when $$$k \geq 3$$$. Together with $$$L(3) \in \{2, 8\}$$$, we have $$$\frac{L(L(10^k))}{10^{k - 2}} \in \{3, 12, 75, 100\}$$$ when $$$k \geq 5$$$. Cases for smaller $$$k$$$ are trivial, and by the way, for convenience of computing, we can calculate the $$$P$$$-Fibonacci sequence in modulo $$$3 \cdot 10^k$$$ when $$$k \geq 3$$$, which is the lowest common multiple of all possible modulo numbers.

Then, we have to prove another insight~--- for any value $$$v$$$, the number of positions $$$x$$$ such that $$$F_x \equiv v \pmod{10^k}$$$ is small. Obviously, it only depends on the number of possible values $$$F_{x - 1}$$$, as each possible pair $$$(F_{x - 1}, F_x)$$$ appears in a period only once. As we know $$$\mathrm{det}(A^x) = \mathrm{det}^x(A) = (-1)^x$$$ and $$$\mathrm{det}(A^x) = F_{x - 1} F_{x + 1} - F^2_x$$$, we can get a equation $$$F^2_{x - 1} + P F_x F_{x - 1} - F^2_{x} \equiv (-1)^x \pmod{10^k}$$$, which can be rewritten as in the form of $$$(2 u + a)^2 \equiv b \pmod{4 \cdot 10^k}$$$, when $$$F_x$$$ and the parity of $$$x$$$ are given.

The number of solutions $$$x$$$ in modulo $$$2^{k + 2} \cdot 5^k$$$ for the equation $$$x^2 \equiv y$$$ is the product of numbers of solutions in modulo $$$2^{k + 2}$$$ and $$$5^k$$$ separately, so we only care about the number of solutions in modulo a power of a prime $$$p^e$$$. Let's discuss in several cases.

1. When $$$y \equiv 0 \pmod{p^e}$$$, each solution $$$x$$$ only needs to satisfy $$$p^{\left \lceil e / 2 \right \rceil} | x$$$, so the number of solutions is $$$p^{\left \lfloor e / 2 \right \rfloor}$$$;
2. When $$$y = p^u \cdot v$$$, $$$1 \leq u < e$$$, $$$p \nmid v$$$, if there exists any solution, then $$$2 | u$$$ and $$$p^{u / 2} | x$$$. Assuming that the number of solutions for the equation $$${x'}^2 \equiv v \pmod{p^{e - u}}$$$ be $$$cnt$$$, the number of solutions for the equation $$$x^2 \equiv y \pmod{p^e}$$$ is $$$p^{u - u / 2} cnt$$$;
3. When $$$p \nmid y$$$ and there exists a primitive root $$$g$$$ in modulo $$$p^e$$$ (i.e. $$$p$$$ is odd or $$$e \leq 2$$$), let $$$x \equiv g^u, a \equiv g^v \pmod{p^e}$$$, and then we know $$$2 u \equiv v \pmod{\varphi(p^e)}$$$, which is a linear congruence having at most $$$2$$$ solutions;
4. When $$$p \nmid y$$$, $$$p = 2$$$, $$$e > 2$$$, we can use a pseudo-primitive root $$$g'$$$ to represent all values in modulo $$$p^e$$$ as in the form of $$$(-1)^u {g'}^v$$$, so it tells us the number of solutions is at most $$$4$$$.

Since $$$\gcd(P, 10^{18}) \in \{1, 2, 4\}$$$, we don't have to handle some larger cases, such as, finding $$$x$$$ with $$$F_x \equiv 1 \pmod{10^k}$$$, when $$$k = 18$$$, $$$P = 10^{k / 2}$$$, in which case the $$$P$$$-Fibonacci sequence is $$$[0, 1, P, 1, 2 P, 1, 3 P, \ldots]$$$, and the number of positions for $$$1$$$ is $$$\frac{10^k}{P} = 10^{k / 2}$$$. Therefore, based on the above rules and a few discussions, we can conclude that for any $$$k$$$, the number of solutions in $$$[0, L(10^k))$$$ for $$$F_x \equiv v \pmod{10^k}$$$ is at most $$$8$$$. (Although $$$(2 u + a)^2 \equiv b \pm 1 \pmod{4 \cdot 10^k}$$$ has $$$16$$$ solutions $$$u$$$ in modulo $$$2 \cdot 10^k$$$, every two solutions $$$u$$$ are equivalent in modulo $$$10^k$$$.) This can help us avoid any calculation about quadratic congruences. That is, we can find all solutions in modulo $$$10^e$$$ and transform them into solutions in modulo $$$10^{e + 1}$$$. More specifically, for each solution $$$x \equiv x_0 \pmod{L(10^e)}$$$ for the former case, we can examine if $$$x \equiv x_0 + t \frac{L(10^{e + 1})}{L(10^e)} \pmod{L(10^{e + 1})}$$$ is a solution for the latter case, and that works very efficiently. Note that when it comes to finding $$$y \equiv F_x \pmod{L(10^k)}$$$, the number of solutions may double.

If we just find solutions for $$$F_x \equiv F_{F_n} \pmod{10^k}$$$ and $$$y \equiv F_x \pmod{L(10^k)}$$$ forcibly, the time complexity will be $$$\mathcal{O}(8 \cdot 16 \cdot (120 + 10 k))$$$. If we prepare some information for $$$k < 3$$$, the time complexity can be even better.

Since every non-special cell has no traversable edge, we can only build an undirected graph for special cells, and the problem can be formed as calculating the cost of a minimum $$$s$$$-$$$t$$$ cut for every two nodes.

In fact, Gomory-Hu tree shows that we can build a weighted tree for these nodes such that each min-cut can be represented as the minimum value on the path between the source and the sink. If we can build the tree, we can easily get the answer by adding edges in decreasing order of weight.

To build the tree, we need to calculate $$$(|V| - 1)$$$ times min-cut. Fortunately, the degree of each node is at most $$$6$$$, which implies the cost of any min-cut is at most $$$6$$$, so we can use Dinic's algorithm to calculate min-cut forcibly, and the time complexity is $$$\mathcal{O}(6 |V| (|V| + |E|))$$$, where $$$|V| \leq 3000$$$, $$$|E| \leq 3 |V|$$$.

A well-known implementation uses `divide and conquers' to build the tree with vertex contractions, however, we can do it more easily. Here is a brief introduction to Gusfield's algorithm, which is also used in this problem's standard program:

• Label nodes from $$$0$$$ to $$$(|V| - 1)$$$, and set the parent of node $$$i$$$ ($$$i = 1, 2, \ldots, |V| - 1$$$) as $$$0$$$;
• For each node $$$i$$$ ($$$i = 1, 2, \ldots, |V| - 1$$$):
  • Find a min-cut $$$(S, T)$$$ between $$$i$$$ and its parent $$$p_i$$$, where $$$i \in S$$$, $$$p_i \in T$$$;
  • For each node $$$j$$$ such that $$$i < j$$$, $$$j \in S$$$, $$$p_j = p_i$$$, set $$$p_j$$$ as $$$i$$$.

Let $$$n = \sum_{i = 0}^{e}{a_i k^i}$$$, such that $$$a_0, a_1, \ldots, a_e$$$ are all integers between $$$0$$$ and $$$(k - 1)$$$ and $$$a_e > 0$$$. We can conclude when $$$f^m(n) = 1$$$, $$$m = e - 2 + \sum_{i = 0}^{e}{a_i}$$$.

Let's partition the interval $$$[l, r + 1)$$$ into many non-intersect subintervals, such that each subinterval is like $$$[a + b k^u, a + c k^u)$$$, where $$$a$$$ is a multiple of $$$k^{u + 1}$$$, and $$$b$$$, $$$c$$$ are integers between $$$0$$$ and $$$k$$$. Since $$$a + b k^u > 0$$$, there is only one possible $$$n = a + c k^u - 1$$$ with the maximum $$$m$$$ in each subinterval. Like working on the segment tree, we can find $$$\mathcal{O}(\log_k{n})$$$ subintervals, and merge their information to get the answer.

By the way, you may notice that $$$m$$$ must be from an integer $$$n$$$ whose length in the base of $$$k$$$ is either $$$e$$$ or $$$(e - 1)$$$, and then discuss $$$11$$$ possible cases.

It is easy to see the lower bound of the answer is $$$\left \lceil \frac{n}{|\Sigma|} \right \rceil$$$, and make it difficult to be passed by a brute-force solution~--- enumerate the position of $$$t_{m / 2 + 1}$$$ and run a DP to find the longest common subsequence (LCS) of two parts. However, we can speed up the process of calculating LCS by bit-level parallelism and pass the tests in time complexity $$$\mathcal{O}\left(\frac{n^3}{w}\right)$$$, where $$$w$$$ is the processor word size (which is $$$64$$$ on $$$64$$$-bit computers).

Assuming that we are finding LCS of $$$s_{1} s_{2} \cdots s_{p}$$$ and $$$s_{p + 1} s_{p + 2} \cdots s_{n}$$$, we can design a DP like $$$dp(i, j)$$$ which means the length of LCS of $$$s_{1} s_{2} \cdots s_{i}$$$ and $$$s_{p + 1} s_{p + 2} \cdots s_{p + j}$$$, and get $$$dp(i, j)$$$ from the maximum of $$$dp(i - 1, j)$$$ and $$$dp(i, j - 1)$$$ when $$$s_{i} \neq s_{p + j}$$$, or otherwise from $$$dp(i - 1, j - 1) + 1$$$.

Note that the transition makes $$$dp(i, j - 1) \leq dp(i, j) \leq dp(i, j - 1) + 1$$$, so we can define $$$f(i, j) = dp(i, j) - dp(i, j - 1)$$$ to convert the information into bits. Let's define $$$g(i, j) = [s_{i} = s_{p + j}]$$$, where $$$[x]$$$ is $$$1$$$ when $$$x$$$ is true, or otherwise $$$0$$$, and then with further discussion or observation, we can get the transition from $$$f(i - 1)$$$ to $$$f(i)$$$ :

• Let $$$x_1$$$, $$$x_2$$$, $$$x_k$$$ be the positions such that $$$1 \leq x_1 < x_2 < \ldots < x_k \leq n - p$$$ and $$$f(i - 1, x_t) = 1$$$ for $$$t = 1, 2, \ldots, k$$$, and define $$$x_0$$$, $$$x_{k + 1}$$$ as $$$0$$$, $$$(n - p + 1)$$$ respectively;
• for each $$$x_t$$$ ($$$t = 1, 2, \ldots, k + 1$$$):
  • find the lowest position $$$u$$$ such that $$$x_{t - 1} < u \leq x_t$$$ and $$$g(i, u) = 1$$$, or in case there is no such $$$u$$$, define $$$u$$$ as $$$x_t$$$;
  • set $$$f(i, u)$$$ as $$$1$$$, and $$$f(i, v)$$$ as $$$0$$$ for $$$v = x_{t - 1} + 1, x_{t - 1} + 2, \ldots, u - 1, u + 1, u + 2, \ldots, \min\{x_t, n - p\}$$$.

The above rule can be interpreted as that, for each interval in $$$f(i - 1)$$$ whose bits are all zeros except for the highest position, find the lowest position in $$$(f(i - 1) | g(i))$$$ that is $$$1$$$ (i.e. ON), and set the interval as all zeros except for the lowest ON position. This can be done by bitwise operations easily, for example, we can use $$$(f(i - 1) < < 1 | 1)$$$ to get the lowest position in each interval, use $$$((f(i - 1) | g(i)) - (f(i - 1) < < 1 | 1))$$$ to make the only difference on the lowest ON position in each interval, and then use other bitwise operations to get them.

Though we can retrieve a needed subsequence from $$$f$$$, you can do a slower DP at the end so that you can get the subsequence without any other thought. In addition, we don't need to calculate $$$g(i)$$$ for each position $$$i$$$ but for each character $$$s_i$$$, and that can be obtained by $$$(n - p)$$$ changes.

By the way, if you are familiar with computing all LCS of a given string $$$A$$$ and each substring of a given string $$$B$$$ in time complexity $$$\mathcal{O}(|A| |B|)$$$, you may find a better solution. This problem is known as the all-substrings longest common subsequence (ALCS) problem.

This is a typical 3D geometry problem. One thing you need to know is the volume of a spherical cap of radius $$$r$$$ and height $$$h$$$, which is

We can prove that no matter how the pivot is selected, each possible permutation for the deeper level appears with equal probability, so the expected number of inversions only depends on the level and the length of the interval.

Let $$$dp(i, j)$$$ be the expected number of inversions when $$$n = i$$$, $$$k = j$$$, and we have

We can calculate partial sums to optimize it into time complexity $$$\mathcal{O}(\max^2\{n\})$$$.

This unweighted graph is formed by $$$k$$$ non-intersect cliques and $$$m$$$ non-intersect chains, so it has many specialties. For example, we can conclude the maximum value of the shortest distance between any two cities is at most $$$(k + k - 1)$$$, as we can pass one edge to all the cities in the same district, and travel to any other city by passing through each district at most once.

If we take the hot air balloon at least once, for example, at the $$$i$$$-th district to travel from city $$$u$$$ to city $$$v$$$, we can conclude the minimum distance is $$$(f(i, u) + f(i, v) + 1)$$$, where $$$f(i, x)$$$ is the shortest distance from $$$u$$$ to any city in the $$$i$$$-th district. Consequently, the shortest distance from $$$u$$$ to $$$v$$$ is either the distance on the railway, if they are on the same railway, or $$$\min_{i = 1}^{k}\{f(i, u) + f(i, v) + 1\}$$$. Since the shortest distance is less than or equal to $$$(k + k - 1)$$$, we can ignore the former case at first, and correct the distence after calculating the latter case.

Let $$$d_u$$$ be the district city $$$u$$$ belongs to, and $$$g(i, j)$$$ be the shortest distance from any city in the $$$i$$$-th district to any city in the $$$j$$$-th district. Then, we have $$$f(i, u) \leq g(i, d_u) + 1$$$, and $$$\min_{i = 1}^{k}\{f(i, u) + f(i, v) + 1\} \leq \min_{i = 1}^{k}\{g(i, d_u) + g(i, d_v) + 3\}$$$.

Let's set a bitmask $$$mask_u$$$ for $$$u$$$ such that the $$$i$$$-th bit is $$$1$$$ when $$$f(i, u) = g(i, d_u) + 1$$$, or otherwise it is $$$0$$$. Then, for each pair of districts $$$(d_u, d_v)$$$, we can discuss the three possible cases of the shortest distance by $$$mask_u, mask_v$$$. For example, if $$$\min_{i = 1}^{k}\{f(i, u) + f(i, v) + 1\}$$$ is obtained from $$$(g(j, d_u) + g(j, d_v) + 1)$$$, then the $$$j$$$-th bit of both $$$mask_u$$$ and $$$mask_v$$$ must be zeros. After precalculating $$$cnt(i, S) = \sum_{d_u = i, mask_u \subseteq S}{1}$$$, we can count for each pair $$$(d_u, d_v)$$$ in time complexity $$$\mathcal{O}(2^k)$$$ by inclusion-exclusion principle.

We can use a breadth-first search to calculate $$$f(i, u)$$$ for each $$$i$$$ in time complexity $$$\mathcal{O}(n)$$$, and enumerate pairs $$$(u, v)$$$ such that $$$u$$$ and $$$v$$$ are on the same railway with distance less than $$$(k + k - 1)$$$ in time complexity $$$\mathcal{O}(n k)$$$, so the total time complexity is $$$\mathcal{O}(n k + k^2 2^k)$$$.

By the way, though we haven't proved it yet, it is showed that the number of different pairs $$$(d_u, mask_u)$$$ is at most $$$k \left({k - 1 \choose 2} + {k - 1 \choose 1} + {k - 1 \choose 0}\right)$$$, and thus it yields a solution in time complexity $$$\mathcal{O}(n k + k^6)$$$.

We call the substring $$$s_{i} s_{i + 1} \cdots s_{j}$$$ a run, denoted by $$$(i, j, d)$$$, if there exists a smallest $$$d$$$ such that

• $$$2 d \leq j - i + 1$$$;
• $$$s_{k} = s_{k + d}$$$ for $$$k = i, i + 1, \ldots, j - d$$$;
• $$$s_{i - 1} \neq s_{i + d - 1}$$$ if $$$s_{i - 1}$$$ exists;
• $$$s_{j + 1} \neq s_{j - d + 1}$$$ if $$$s_{j + 1}$$$ exists.

With respect to a strict total order $$$<$$$ on the alphabet $$$\Sigma$$$, we call a string $$$w$$$ Lyndon word if $$$w < u$$$ is true for each proper suffix $$$u$$$ of $$$w$$$. Since for a run $$$(i, j, d)$$$ we have $$$s_{j + 1} \neq s_{j - d + 1}$$$, we can always find a Lyndon word $$$s_{u} s_{u + 1} \cdots s_{v}$$$ with respect to a strict total order $$$<$$$ or its reversed order, such that $$$v - u + 1 = d$$$ and $$$i < u \leq i + d$$$. Also, it can be proved that different runs don't share any such words, and thus the number of runs is $$$\mathcal{O}(n)$$$.

By further proof, we can get $$$\sum_{(i, j, d)\text{ is a run}}{\frac{j - i + 1}{d}} \leq 3 n - 3$$$, which implies that, if we pick up all the squres as square-triples $$$(L, R, k)$$$ such that each length-$$$k$$$ substring of $$$s_{L} s_{L + 1} \cdots s_{R}$$$ is a square, the number of these square-triples are less than $$$\frac{3}{2} n$$$. If we can pick up these square-triples, we can solve the problem using some data structures.

First, let's talk about how to get these triples. There are many ways to detect runs, and then you can pick up all the square-triples. For example, you can enumerate $$$d$$$ and positions $$$1, d + 1, 2 d + 1, \ldots$$$ in the string so that you can check if two consecutive positions are in the same run and then detect the run. Alternatively, you can linearly build the Lyndon tree of the string and meanwhile get runs. The former detects all runs in time complexity $$$\mathcal{O}(n \log n)$$$, and the latter in $$$\mathcal{O}(n)$$$, in which building the suffix array of the string in linear time is required.

Then, let's see if we can maintain some data structure to solve the problem in time complexity $$$\mathcal{O}((n + q) \log n)$$$. Let's consider the relationship between a query $$$(l_i, r_i)$$$ and a square-triple $$$(L, R, k)$$$. Obviously, if the triple has any contribution to the query, it must have $$$k \leq r_i - l_i + 1$$$. Furthermore, we can split one triple $$$(L, R, k)$$$ into two triples without upper bounds, $$$(L, \infty, k)$$$ and $$$(R - k + 2, \infty, k)$$$, so that we can handle things easily. That is, for a new triple $$$(u, \infty, k)$$$, its contribution (without regard to its sign) to the query $$$(l_i, r_i)$$$ is $$$(\max\{r_i - u - k + 2, 0\} - \max\{l_i - u, 0\})$$$, which can be calculated by maintaining two Fenwick trees and enumerating intervals in increasing order of length.

The number of ways to partition a set of size $$$12$$$ into $$$4$$$ sets of size $$$3$$$ without regard to order is $$$\frac{12!}{3!3!3!3!4!} = 15400$$$. We can find these partitions through a depth-first search, and the problem can be done. By the way, we can sort sticks in increasing order of length so that we can use $$$a < b < c$$$ and $$$a + b > c$$$ to check the existence of a triangle with side lengths $$$a, b, c$$$.

One brute-force way is to enumerate three of $$$\frac{12!}{3!9!}$$$ ($$$= 220$$$) possible sets and prune when it is necessary, however, it can hardly pass all the tests.

The key insight is that, for every three equidistant vertices, we can find the only upright equilateral triangle such that these three vertices are on the triangle's sides. (We can do so for the only inverted equilateral triangle.) Based on this fact, many solutions can be designed.

For example, you can use some data structure to maintain some information for $$$l$$$ when $$$r$$$ is fixed and shifted from low to high, or even you can use Mo's algorithm to solve the problem in time complexity $$$\mathcal{O}(\max\{r\} \sqrt{T})$$$.

If you are very good at math, you can find out the combinatorial form of the answer (a polynomial of degree $$$4$$$), and then solve the problem with or without interpolation.

The answer is $$$\left \lfloor \log_{10} (2^m - 1) \right \rfloor$$$. Apparently, there does not exist $$$10^k = 2^m$$$ for positive integers $$$k$$$, $$$m$$$, which results in $$$\left \lfloor \log_{10} (2^m - 1) \right \rfloor = \left \lfloor \log_{10} 2^m \right \rfloor = \left \lfloor m \log_{10} 2 \right \rfloor$$$.

Each letter's contribution to the answer can be treated as a number in the base of $$$26$$$, so the problem is equivalent to multiply these contributions with weights ranged from $$$0$$$ to $$$25$$$ and thus make the answer maximum. Obviously, the largest contribution matches $$$25$$$, the second-largest matches $$$24$$$, and so on. Doing this greedy algorithm by sorting could be enough, except for the only case where it might cause leading zeros, which is not permitted.

Time complexity is $$$\mathcal{O}\left(\sum_{i = 1}^{n}{|s_i|} + \max(|s_1|, |s_2|, \ldots, |s_n|) \log C\right)$$$, where $$$C = 26$$$.

If we consider the number of paths covered by some color at least once for each color separately, we can conclude the answer is the sum of these numbers. Conversely, we can count how many paths that are not covered by this color, which is easy to compute. We can apply the idea of virtual trees to solve it directly, in which we do not really need to build them out. What we need to calculate is the total number of paths within any blocks after removing all the nodes of a specified color from the tree. We can maintain for each node of this color, the number of remaining nodes whose least ancestor of this color is this node. Together with the number of nodes which has no ancestor of this color, we can get the answer.

The process can be implemented directly by DFS (Depth-First Search) once, so the time complexity is $$$\mathcal{O}(n)$$$.

Apparently, each pile could be operated no more than $$$\sum_{i = 1}^{m}{e_i}$$$ (marked as $$$w$$$) times. Besides, let's define $$$f(x)$$$ as the number of ways to change a pile into one stone by changing exactly $$$x$$$ times, and then it is obvious that $$$f(x)$$$ equals to the number of ways to change a pile into two or more stones by changing $$$(x - 1)$$$ times.

To count the situations ending at the pile labeled $$$i$$$, let's assume and enumerate that this pile has been changed $$$x$$$ times, and then we know the number of corresponding ways is $$$f(x + 1)^{i - 1} f(x)^{k - i + 1}$$$. Hence, we can reduce problem into calculation of $$$f(x)$$$ in time complexity $$$\mathcal{O}(w k)$$$.

Let's consider situations counted in $$$f(x)$$$ and define that, in one possible way, $$$e_i$$$ is decreased by $$$d(i, j)$$$ in the $$$j$$$-th operation, and then we have

• $$$d(i, j)$$$ is a non-negative integer for each $$$(i, j)$$$; and
• $$$\sum_{j = 1}^{x}{d(i, j)} = e_i$$$ for each $$$e_i$$$; and
• $$$\sum_{i = 1}^{m}{d(i, j)} > 0$$$ for each $$$j$$$.

Furthermore, we can conclude that $$$f(x)$$$ equals to the number of different solutions $$$d(i, j)$$$ meeting all the above restrictions.

Let $$$g(x)$$$ be the number of corresponding ways meeting only the first two restrictions. We can observe that it is a combination of combinatorial problems for each $$$e_i$$$, and then figure out $$$g(x) = \prod_{i = 1}^{m}{e_i + x - 1 \choose x - 1}$$$.

We can also observe that if the last restriction is violated by some $$$j$$$, then all those related $$$d(i, j)$$$ must equal to zero. Applying the inclusion-exclusion principle, we have $$$f(x) = \sum_{y = 0}^{x}{(-1)^{x - y} {x \choose y} g(y)}$$$, which can be rewritten as $$$\frac{f(x)}{x!} = \sum_{y = 0}^{x}{\frac{(-1)^{x - y}}{(x - y)!} \frac{g(y)}{y!}}$$$, a formula in the form of convolution. Together with that $$$985661441 = 235 \times 2^{22} + 1$$$ is prime, we can apply NTT to speed up the convolution.

The total time complexity is $$$\mathcal{O}(w (m + \log n + k))$$$.

Let $$$f(n)$$$ be the expected number of operations replacing from $$$n$$$ to $$$1$$$. Specifically, $$$f(1) = 0$$$. Given the process described in the statement, we have

where $$$n > 1$$$, and $$$\sigma(n)$$$ is the number of positive factors of $$$n$$$.

Obviously, even if we try to furtherly simplify the formula, we can hardly compute $$$f(n)$$$ before determining $$$f(d)$$$ for all $$$d | n, d < n$$$. Based on this observation, our first step to solve this problem is to reduce the amount of calculation required for all $$$f(n)$$$. For two positive integers $$$x$$$ and $$$y$$$, if their prime factorizations $$$x = \prod_{i = 1}^{m}{{p_i}^{e_i}}$$$, $$$y = \prod_{i=1}^{m'}{{p'_i}^{e'_i}}$$$ meet the condition that $$$\lbrace e_i | i = 1, 2, \ldots, m \rbrace = \lbrace e'_i | i = 1, 2, \ldots, m' \rbrace$$$, then we can conclude $$$f(x) = f(y)$$$ by induction. Based on this conclusion, when computing $$$f(n)$$$, we can simply ignore its prime factors and only focus on the unordered multiset formed by the corresponding exponents in its prime factorization.

Our next step is to figure out the number of possible multisets is fairly small, with the restriction $$$n \leq 10^{24}$$$. If a multiset of exponents $$$E$$$ is possible, then the minimum possible $$$n$$$ corresponding to it must be no larger than $$$10^{24}$$$. Let the minimum possible $$$n$$$ for the multiset $$$E$$$ be $$$\mathrm{rep}(E)$$$ and the prime factorization of $$$\mathrm{rep}(E)$$$ be $$$\sum_{i = 1}^{m}{{p_i}^{e_i}}$$$, and we can conclude (by a standard interchange argument) that $$$e_u \geq e_v$$$ for all $$$1 \leq u, v \leq m$$$, $$$p_u < p_v$$$. Furthermore, as $$$m \leq \log_2 n$$$ and these prime factors must be the $$$m$$$ smallest prime numbers, all possible $$$\mathrm{rep}(E)$$$ can be detected by backtracking in time complexity $$$\mathcal{O}(|S|)$$$, where $$$S$$$ is the set of all possible multisets. When $$$n \leq 10^{24}$$$, $$$|S| = 172513$$$, which is not too large, so let's use hashing to memorize all corresponding $$$f(n)$$$, and optimize the calculation for each multiset.

For each multiset $$$E$$$, we cannot enumerate all factors of $$$\mathrm{rep}(E)$$$, because when $$$n \leq 10^{24}$$$, $$$\sigma(n) \leq 1290240$$$ and $$$\sum_{E \in S}{\sigma(\mathrm{rep}(E))} = 14765435692 \approx 1.5 \times 10^{10}$$$, which seems too gigantic to pass the test.

Another way is to apply the inclusion-exclusion principle. Let $$$g(n) = \sum_{d | n, d < n}{f(d)}$$$, $$$h(n) = g(n) + f(n)$$$, and then we have $$$f(n) = \frac{\sigma(n) + g(n)}{\sigma(n) - 1}$$$, and

where $$$n = \prod_{i = 1}^{\omega(n)}{{p_i}^{e_i}}$$$, $$$\omega(n)$$$ is the number of distinct prime factors of $$$n$$$, and $$$J = \lbrace p_i | i = 1, 2, \ldots, \omega(n) \rbrace$$$. However, just applying the above formula cannot easily pass the test, because when $$$n \leq 10^{24}$$$, $$$\omega(n) \leq 18$$$ and $$$\sum_{E \in S}{2^{\omega(\mathrm{rep}(E))}} = 103800251 \approx 10^8$$$, which is still too massive to pass. By the way, most calculations are additions and substractions on floating-point numbers, so maybe you can squeeze your program to pass the time limit (and actually some team did it).

Note that $$$h(n) = \sum_{d | n}{f(d)}$$$ is essentially computing a partial sum for $$$\omega(n)$$$-dimensional integer vectors, and can be improved by using extra space. Assuming $$$n = \prod_{i = 1}^{\omega(n)}{{p_i}^{e_i}}$$$ and $$$p_i < p_{i + 1}$$$ for $$$1 \leq i < \omega(n)$$$, let's define that

for $$$0 \leq k \leq \omega(n)$$$, and then we can get $$$g(n, k)$$$ from $$$h(n, k - 1)$$$ and $$$h(n / p_k, k')$$$, where $$$k'$$$ is either $$$k$$$ or $$$(k - 1)$$$, which only depends on whether $$$n / p_k$$$ is a multiple of $$$p_k$$$.

Finally, we have to replace $$$n$$$ by the corresponding multiset $$$E$$$, where we had better choose the minimum possible $$$n$$$ as $$$\mathrm{rep}(E)$$$ and only calculate $$$h$$$, $$$g$$$ for all $$$\mathrm{rep}(E)$$$, because its exponents are sorted in non-decreasing order, which can keep the number of related states minimized.

After all these simplifications, we find a solution that runs in time and space complexity $$$\mathcal{O}\left(\sum_{E \in S}{\omega(\mathrm{rep}(E))}\right) = \mathcal{O}(|S| \omega(n))$$$. When $$$n \leq 10^{24}$$$, $$$\sum_{E \in S}{\omega(\mathrm{rep}(E))} = 1173627 \approx 10^6$$$, which is small enough.

In practice, arithmetic operations on huge integers are not complicated to code and can be implemented in constant time, so the total time complexity is $$$\mathcal{O}(|S| \omega(n) + T \log n)$$$, where $$$T$$$ is the number of test cases.

A permutation can be decomposed into one or more disjoint cycles, which are found by repeatedly tracing the application of the permutation on some elements.

For each element $$$i$$$ in a $$$l$$$-cycle of permutation $$$a$$$, we have

which implies $$$f(i)$$$ must be some element in a cycle of permutation $$$b$$$, whose length is a factor of $$$l$$$.

Besides, if $$$f(i)$$$ is fixed, the other $$$(l - 1)$$$ numbers in this cycle can be determined by $$$f(i) = b_{f(a_i)}$$$.

Consequently, the answer is $$$\prod_{i = 1}^{k} \sum_{j | l_i} {j \cdot c_j}$$$, where $$$k$$$ is the number of cycles obtained from permutation $$$a$$$, $$$l_i$$$ represents the length of the $$$i$$$-th cycle, and $$$c_j$$$ indicates the number of cycles in permutation $$$b$$$ whose length are equal to $$$j$$$.

Due to $$$\sum_{i = 1}^{k} \sum_{j | l_i}{1} \leq \sum_{i = 1}^{k}{2 \sqrt{l_i}} \leq 2 \sqrt{k \sum_{i = 1}^{k}{l_i}} \leq 2 n$$$, the time complexity is $$$\mathcal{O}(n + m)$$$.

The gears with their adjacency relations form a forest. We can consider coaxial gears, which have the same angular velocity, as a block and then consider the effect of gear meshing.

If the $$$x$$$-the gear and the $$$y$$$-th one mesh, let their radii be $$$r_x$$$, $$$r_y$$$ respectively, and let their angular velocities be $$$\omega_x$$$, $$$\omega_y$$$ respectively, and then we have $$$\ln \omega_y = \ln \omega_x + \ln r_x - \ln r_y$$$. Hence, for a particular gear in a connected component, we can determine the difference of angular velocities between this gear and any other gear in the component, and then maintain the maximum relative difference using a segment tree on the traversal sequence obtained from DFS (Depth-First Search).

More specifically, let's fix a gear in each component as the reference gear and maintain the differences for all gears in this component. Let the fixed gear be the root of this component, and then we build a segment tree to maintain the maximum value on the rooted tree structure of this component.

When a gear is replaced, the angular velocity of its block may be changed if it is the shallowest node in this block, and the angular velocity of other blocks may be changed if these blocks are completely contained in the subtree of the changed node. No matter in which case, there is only an interval of the traversal sequence corresponding to the nodes needed to update by adding a common offset on their record values.

For each query, we only need to get the difference between the activated gear and the reference gear. Together with the maximum relative difference in the component, the real maximum angular velocity can be determined.

In practice, you can maintain $$$\log_2 \omega$$$ to avoid possible precision issues and only convert it into $$$\ln \omega$$$ for the output.

Time comlexity is $$$\mathcal{O}(n + m + q \log n)$$$.

Let's sort these hints in non-increasing order and remove duplicates. Denote the sorted array as $$${b'}_{1}$$$, $$${b'}_{2}$$$, $$$\ldots$$$, $$${b'}_{m'}$$$ satisfying $$${b'}_{i} < {b'}_{i - 1}$$$ for each $$$i \geq 2$$$, and define that $$${b'}_{0} = n$$$.

One solution to this problem is to apply a linear selection algorithm, which can find the $$$k$$$-th smallest element in an array of length $$$n$$$ in time complexity $$$\mathcal{O}(n)$$$ and also split the array into three parts that include the smallest $$$(k - 1)$$$ elements, the $$$k$$$-th element and other elements respectively.

Due to $$$b_i + b_j \leq b_k$$$ if $$$b_i \neq b_j$$$, $$$b_i < b_k$$$, $$$b_j < b_k$$$, we have $$$2 {b'}_{i} < {b'}_{i - 2}$$$ for each $$$i \geq 3$$$. We can conclude $$$\sum_{k}{{b'}_{2 k + 1}} < 2 {b'}_{1}$$$ and so for elements on even positions.

If the algorithm is completely linear, the time complexity should be $$$\mathcal{O}\left(\sum_{i = 0}^{m' - 1}{{b'}_{i}}\right) = \mathcal{O}(n)$$$. Since ratings are almost generated at random, we can instead utilize an almost linear approach, such as nth_element function in C++. By the way, there exist solutions in expected time complexity $$$\mathcal{O}(\sqrt{n m'})$$$.

As the graph is a cactus graph, it is no doubt that one edge of each cycle needs to be removed in order to make a spanning tree. Hence, the problem can be rewritten as that we have $$$M$$$ ($$$M \leq \frac{m}{3}$$$) arrays consisting of integers and we want to pick a number from each array so that we can get their sum, however, we want you to find possible ways with the largest $$$K$$$ sums and report the sum of these values.

It is a classic problem that can be solved by sequence merge algorithms, for example, we can maintain a set of $$$K$$$ largest values obtained from the first $$$x$$$ arrays, and then merge it with the $$$(x + 1)$$$-th array and find $$$K$$$ largest new values by using a heap or priority queue. More specifically, let's assume that we are going to merge two non-increasing arrays $$$A$$$, $$$B$$$ and pick $$$K$$$ largest values obtained from $$$(A_i + B_j)$$$. As we know $$$B_j \geq B_{j + 1}$$$, so if we pick $$$(A_i + B_{j + 1})$$$, we must pick $$$(A_i + B_j)$$$ first. That inspires us to set a counter $$$c_i$$$ for each $$$A_i$$$, which represents if we will pick $$$A_i$$$ with some value, we are going to pick $$$(A_i + B_{c_i})$$$. Then, we can use a data structure to maintain the set of all possible $$$(A_i + B_{c_i})$$$ and then query and erase the largest value, which we can just repeat at most $$$K$$$ times to get all the merged values we need.

It seems the above method runs in time complexity $$$\mathcal{O}(MK \log K)$$$, but actually, it can run faster. Let the sizes of these arrays are $$$m_1$$$, $$$m_2$$$, $$$\ldots$$$, $$$m_M$$$ ($$$m_i \geq 3$$$ for each $$$i$$$) respectively. If we instead to maintain $$$(A_{c_j} + B_j)$$$ in the data structure, where $$$B$$$ is the next array to be merged, the complexity will be $$$\mathcal{O}\left(\sum_{i = 1}^{M}{K \log{m_i}}\right) = \mathcal{O}\left(K \log{\prod_{i = 1}^{M}{m_i}}\right) = \mathcal{O}\left(M K \log{\frac{\sum_{i = 1}^{M}{m_i}}{M}}\right) = \mathcal{O}\left(M K \log{\frac{m}{M}}\right)$$$. As $$$M \leq \frac{m}{3}$$$, we can conclude the worst complexity is $$$\mathcal{O}(m K)$$$, when $$$M = \frac{m}{3}$$$.

By the way, there exist solutions in time complexity $$$\mathcal{O}(K \log K)$$$.

The main idea of our standard solution is ordinary generating function. Let's define the number of ways to choose food of total volume $$$k$$$ as $$$f(k)$$$, and its generating function as $$$F(z) = \sum_{k \geq 0}{f(k) z^k}$$$. After calculating the polynomial $$$(F(z) \bmod z^{2 n + 1})$$$ with coefficients in modulo $$$(10^9 + 7)$$$, we can enumerate one of equipment and calculate the answer.

Based on the rule of product, we have

Due to $$$0 \leq a_1 < a_2 < \ldots < a_n$$$, we know that $$$a_i \geq i - 1$$$ and thus $$$(a_i + 1) i \geq i^2$$$, which implies there are only $$$\mathcal{O}(\sqrt{n})$$$ items $$$\left(1 - z^{(a_i + 1) i}\right)$$$ that are not equivalent to $$$1$$$ in modulo $$$z^{2 n + 1}$$$. Hence, we can calculate the numerator of $$$(F(z) \bmod z^{2 n + 1})$$$ in time complexity $$$\mathcal{O}(n \sqrt{n})$$$.

The rest is similar to the generating function of partition function. That is defined as

where $$$p(k)$$$ represents the number of distinct partitions of a non-negative integer $$$k$$$. Pentagonal number theorem states that

which can help us calculate the polynomial $$$(P(z) \bmod z^m)$$$ in time complexity $$$\mathcal{O}(m \sqrt{m})$$$. Besides, $$$1 - x^k \equiv 1 \equiv \frac{1}{1 - x^k} \pmod{x^m}$$$ for any integers $$$k \geq m \geq 1$$$, so we have

and we can get the denominator of $$$(F(z) \bmod z^{2 n + 1})$$$ from $$$(P(z) \bmod z^{2 n + 1})$$$ easily.

The total time complexity can be $$$\mathcal{O}(n \sqrt{n})$$$ if we calculate the denominator as a polynomial first, and then multiply it with each term included in the numerator one by one. By the way, if you are familiar with polynomial computation, you can solve the problem in time complexity $$$\mathcal{O}(n \log n)$$$.

The answers for fixed $$$n$$$ form an almost periodic pattern. It is not difficult to find out that is $$$\underbrace{1, 2, \ldots, n}_{n \text{ numbers}}$$$, $$$\underbrace{1, 2, \ldots, n - 1}_{(n - 1) \text{ numbers}}$$$, $$$\underbrace{1, 2, \ldots, n - 2, n}_{(n - 1) \text{ numbers}}$$$, $$$\underbrace{1, 2, \ldots, n - 1}_{(n - 1) \text{ numbers}}$$$, $$$\underbrace{1, 2, \ldots, n - 2, n}_{(n - 1) \text{ numbers}}$$$, $$$\ldots$$$

According to $$$(l_i, r_i)$$$, we can build the only Cartesian tree linearly. If there is any contradiction, the answer should be $$$0$$$. Besides, it is not difficult to conclude the Cartesian tree, if exists, is unique.

More specifically, we can find out each node of the tree recursively. For example, the root must cover the interval $$$[1, n]$$$, and if a node $$$u$$$ cover the interval $$$[L, R]$$$, then its left child, if exists, must cover $$$[L, u - 1]$$$, and its right child, if exists, must cover $$$[u + 1, R]$$$. If there is no position $$$u$$$ covering the whole interval $$$[L, R]$$$, we will find a contradiction. If there are multiple choices, we will find a contradiction too, but we can just choose any of them as $$$u$$$ because further checking will detect contradictions. Hence, after sorting given intervals by radix sort, we can construct the tree linearly.

The counting can be done recursively as well. Let $$$s(u)$$$ be the size of the subtree of the node $$$u$$$, which is also equal to $$$(r_u - l_u + 1)$$$, and $$$f(u)$$$ be the number of permutations obtained from $$$1$$$ to $$$s(u)$$$ that can form the same Cartesian tree as the subtree of the node $$$u$$$. If the node $$$u$$$ has two chilldren $$$v_1$$$, $$$v_2$$$, we have $$$f(u) = {s(v_1) + s(v_2) \choose s(v_1)} f(v_1) f(v_2)$$$. By the way, if we explore a bit more, we will find the answer is also equal to $$$\frac{n!}{\prod_{i = 1}^{n}{s(i)}}$$$.

Time complexity is $$$\mathcal{O}(n)$$$. The bottleneck is on reading the input data.

By contradiction, we can prove that for an undirected graph, each edge belongs to at most one cycle if and only if there are at most two non-intersect paths between any two vertices. In addition, the maximum flow problem and the minimum cut problem are equivalent, so we only need to consider how to cut some edges with the lowest sum of capacities so that the source vertex $$$s$$$ is not connected to the sink vertex $$$t$$$.

Let's take a look at the $$$s$$$-$$$t$$$ cut problem. If there are at least two edges in one cycle that are cut, we can figure out by adjustment that at most two of edges in this cycle should be cut, since there are at most two non-intersect paths between $$$s$$$ and $$$t$$$. In addition, if there are many cycles where some edges of each cycle are cut, it can be known by adjustment and contradiction that, under the optimal strategy, at most one cycle can contain edges to be cut.

One observation is that if there is at least one edge in a cycle should be cut in an optimal way, there must be exactly two edges to be cut, and one of them must be the edge with the smallest capacity. Hence, we can remove the edge with the smallest capacity in each cycle and then add its capacity to the other edges in the cycle, which won't change the maximum flow between any two vertices in value.

The reduced graph forms a tree. If we add these edges in descending order of its capacity from scratch, we can determine $$$\mathrm{flow}(s, t) = w$$$ $$$(s \in S, t \in T)$$$ for the two sets of vertices $$$S$$$ and $$$T$$$ that are firstly connected after joining the edges with capacities no less than $$$w$$$.

We can maintain these sets of vertices by the disjoint set union and count in each set the number of vertices whose bits in some fixed position are $$$1$$$, and then it is easy to calculate the answer by enumerating each bit. Time complexity is $$$\mathcal{O}(m \log n)$$$.

Note that $$$\mathrm{flow}(s, t)$$$ can be $$$2 \times 10^9$$$, which means the answer may exceed $$$2^{63}$$$. To reach the peak value, we can just construct a circle with edges of the same weight $$$10^9$$$.

When enumerating bits, we can treat the lowest $$$(\log n)$$$ bits and other bits differently, which explains why the time complexity is $$$\mathcal{O}(m \log n)$$$ rather than $$$\mathcal{O}(m \log w)$$$.

For each permutation of positions, the minimum number of swaps equals to $$$n$$$ minus the number of disjoint cycles in the permutation.

We can solve the problem by enumerating all the $$$n$$$-permutations. For each permutation, we only need to check if it can be reached within $$$k$$$ swaps as swapping the same position is permitted.

Time complexity is expected to be $$$\mathcal{O}(m!)$$$, where $$$m = \left \lfloor \log_{10} n \right \rfloor + 1$$$. In order to achieve that, we can maintain some information about chains and cycles so that we can modify and retrieve efficiently during backtracking.

For each permutation of positions, the minimum number of swaps equals to $$$n$$$ minus the number of disjoint cycles in the permutation.

We can precalculate the minimum number of steps to obtain a permutation from the original one, and then enumerate permutations and update the answer. Time complexity is $$$\mathcal{O}\left(\sum_{i = 1}^{9}{(i \cdot i!)} + T m!\right)$$$, where $$$m = \left \lfloor \log_{10} n \right \rfloor + 1$$$.

Some solution cannot handle the case $$$n = 10^9$$$, but it can be solved by hand.

Many greedy solutions can be hacked even by random tests, so... the dataset is almost randomized. :P

As we know, the Möbius inversion formula can be expressed as

where $$$\mu$$$ is the Möbius function and the sums extend to all positive divisors $$$d$$$ of $$$n$$$.

Similarly, we can obtain the following formula.

If we apply this formula, the problem can be solved in $$$\mathcal{O}(2^{\omega(n)} n)$$$, where $$$\omega(n)$$$ means the number of distinct prime factors of $$$n$$$. To prove that, you need to know what the Möbius function is, and observe that $$$f(n)$$$ in this problem is a polynomial with only two non-zero terms. In addition, $$$\sum_{d | n}{\varphi(d)} = n$$$.

By the way, $$$\omega(n) \leq 6$$$ when $$$n \leq 10^5$$$, because $$$2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 = 510510$$$.

Q: Why does Fast Fourier Transform get a verdict of TLE? It seems $$$\log n \sim 2^{\omega(n)}$$$ when $$$n \leq 10^5$$$.

A: FFT implies big constant factor. Also, the above solution does not require floating point operation.

The union is difficult to compute but the intersection is easy, so let's apply $$$|S_u \cup S_v| = |S_u| + |S_v| - |S_u \cap S_v|$$$, where $$$S_x$$$ is the set of vertices whose distances to $$$x$$$ are no more than $$$w$$$.

Note that the tree is not changed, so you can precalculate the structure of its centroid decomposition, in order to calculate $$$|S_u|$$$ online.

Since the restricted distances are the same, if $$$S_u$$$ and $$$S_v$$$ have a non-empty intersection, their intersection will equal to the set of vertices whose distances to the middle point of the path between $$$u$$$ and $$$v$$$ are no more than $$$\left(w - \frac{dist(u, v)}{2}\right)$$$, which can be counted similarly. To avoid many discussions, you can add extra vertices at the middle points of edges.

Time complexity and space complexity are both $$$\mathcal{O}(n \log n)$$$. However, some solution may lose out due to cache-unfriendly behaviors. One way to ease that is to discuss the situations instead.

Note that the cutting areas do not intersect, which implies the different cutting areas do not affect each other, so we can reduce the problem into calculating angles of triangles. Cosine theorem would be helpful.

Anyway, you can paste your geometry coding template to solve, but it seems like overkill.

Though the data range is small, we should be careful calling functions like acos(x) where $$$x$$$ should be ranged in $$$[-1, 1]$$$, or otherwise NaN will give you a lesson.

The statement is a bit different from the above, however, the meanings are equivalent based on Dilworth's theorem.

We may be familiar to the case that $$$p_i = 2$$$ for all $$$i$$$, which is equivalent to find a maximal subset of the power set of some set $$$S$$$ such that none of the sets is a strict subset of any other. Besides, the conclusion, also known as Sperner's theorem, is that the size of the maximal subset is $$${|S| \choose \left \lfloor |S| / 2 \right \rfloor}$$$.

A generalization of Sperner's theorem could show the answer to this problem is the number of points satisfying $$$\sum_{i}{x_i}$$$ is equal to $$$M = \left \lfloor \frac{1}{2} \sum_{i}{(p_i + 1)} \right \rfloor$$$. The proof is similar so we omit it.

Then, as we solve many counting problems in the form of $$$\sum_{i}{x_i} = M~(1 \leq x_i \leq p_i)$$$, we can use inclusion-exclusion principle to get the answer

where $$$J = {1, 2, \ldots, n}$$$.

The remaining part is straightforward. We can regard $$${M - 1 - \sum_{i \in I}{p_i} \choose n - 1}$$$ as a low-degree polynomial of $$$\sum_{i \in I}{p_i}$$$ and use the meet-in-the-middle approach to split $$$I$$$ into two two halves almost evenly. Time complexity is $$$\mathcal{O}(2^{n / 2} n^2)$$$.

Queries and changes don't appear in turns, so we can solve the problem offline. We can build a sparse table to postpone changes like lazy propagation on segment tree.

For each operation $$$(l, r, v)$$$, let $$$d$$$ be $$$\left \lfloor \log_2(r - l + 1) \right \rfloor$$$, and replace this operation by two operations $$$(l, l + 2^d - 1, v)$$$ and $$$(r - 2^d + 1, r, v)$$$. Then each operation is able to be recorded in the sparse table. Also, it is convenient that when there are two operations covering the same interval, we can just keep the one with a higher value. After that, we split each recorded operation into two smaller ones in decreasing order of length. We do it repeatedly until the length of intervals is $$$1$$$, and then we get the answer.

Time complexity is $$$\mathcal{O}(m + n \log n)$$$ and space complexity is $$$\mathcal{O}(n \log n)$$$.

We can apply radix sort carefully and cache-friendly so that we are able to enumerate operations in decreasing order of value. Then using some trick to hit each position almost once may lead to success.

However, due to cache-unfriendly behaviors, there was only one team that used it to get accepted. We do not recommend using this solution because it requires optimization techniques.

Due to the randomness of operations, there are several approaches to pass.

For example, if we assume the number of useful operations is almost $$$\min(m, 2 n)$$$, we can use a linear approach to find operations with the largest $$$\min(m, 2 n)$$$ values, and then do whatever you want to solve this problem.

Another example is using the trick mentioned in Segment tree beats, created by Syloviaely. Amazingly, during the contest, there were tremendous Chinese teams using this approach to pass, even though many of them didn't comprehend its amortized complexity analysis.

You can write a typical DP to solve, but notice that the more complex your solution is, the more tiresome retrieving will be.

One elegant way is to enumerate the value range $$$[x, y]$$$ that needs to be reversed. In doing so, we only need to find find the longest subsequence in the form of $$$0^* 1^* \ldots x^* y^* (y - 1)^* \ldots x^* y^* (y + 1)^* \ldots 9^*$$$, where $$$k^*$$$ represents any non-negative times of occurrences of integer $$$k$$$. It also makes retrieving easy to implement.

This idea has been noticed in the tutorial for 933A - A Twisty Movement, created by visitWorld. Time complexity is $$$\mathcal{O}(D^3 n)$$$, where $$$D = 10$$$ is the maximal number of distinct values.

Let's solve an easier version first. In this version, we are given $$$N, {R_i}, K$$$ and we have to choose $$$N$$$ integers $$$x_1, x_2, \ldots, x_N$$$ such that $$$x_i \in [0, R_i]$$$ for all $$$i$$$, and the bitwise XOR of them equals to $$$K$$$. Similar problems can be found at Crystals — POI 2006 and Stone Game — Hackerrank.

In case that $$$x_i \in [0, 2^m - 1]$$$ for all $$$i$$$, we know the problem is related to XOR equation on bits. Furthermore, when $$$(N - 1)$$$ ones of these variables are fixed, the rest one is determined. So if any solution exists, the number of solution is always $$$2^{m (N - 1)}$$$, no matter what $$$K$$$ is.

If we apply digit DP on bits, we can classify all the situations into different groups by the highest digit satisfying that there exists at least one variable $$$x_j$$$ which is strictly less than $$$R_i$$$ on this digit. Then, we know the lower bits of $$$x_j$$$ can be arbitrary, so we can leave its lower bits first and determine that by equation after other variables are enumerated and fixed. It is not difficult to design a digit DP to count. Time complexity for this part is $$$\mathcal{O}(N \log R)$$$.

Now let's turn back to the harder version, where $$$N$$$ becomes bigger and the lower bound of $$$x_i$$$ is limited. First, we can apply the inclusion-exclusion principle to eliminate the extra lower bound, in other words, we reduce it into many states in which either $$$x_i \in [0, R]$$$ or $$$x_i \in [0, L - 1]$$$ is satisfied. Then, let's take a look at the digit DP. We can record the sign caused by the inclusion-exclusion principle, and thus boost the same transition of DP using fast power algorithm on matrix multiplications. Time complexity is $$$\mathcal{O}((8^3 \log N + Q) \log R)$$$.

Oops... It seems like I've missed an important part — why matrix multiplications can reduce $$$2^N$$$ states into $$$2$$$ states. On each bit, we keep the higher bits as the same as the upper bounds, use DP to ensure at least one variable $$$x_j$$$ exists and determine XOR sum on this bit, and then determine the lower bits by XOR equation. The only difference among states is due to the upper bounds of the higher bits when we apply the inclusion-exclusion principle. Fortunately, their bitwise XOR sums differ when the parities of the numbers of upper bounds that are $$$R$$$ differ, so we can record the parity, which is equivalent to the sign caused by the inclusion-exclusion principle, to reduce the states.

Based on the fact observed in case that $$$x_i \in [0, 2^m - 1]$$$, many solutions can get accepted.

For example, let $$$dp(i, j)$$$ be the number of sequences $$$x_1, x_2, \ldots, x_i$$$ such that their XOR sum is $$$j$$$. We can observe for each $$$i$$$, values of $$$dp(i, j)$$$ can be split into several intervals with respect to $$$j$$$ such that values in each interval are the same. Maintaining these intervals can get accepted, as the number of intervals seems to be $$$\mathcal{O}(\log R)$$$, which is not relevant to $$$N$$$.

Tester quailty: If we exploit this property more deeply, we can get the exact formula and solve the problem in time complexity $$$\mathcal{O}((10 \log N + Q) \log R)$$$.

A simpler version can be found at GuessTheSubstring -- TCO 2011 Semifinal 1 500, created by misof. The harder version increases the upper bound of $$$n$$$ and requires high precision.

Before introducing our linear solution, we have to confess that it is too hard to create a dataset against solutions in time complexity $$$\mathcal{O}(n \log n)$$$. Why are judging machines so fast? If anyone has ideas to improve the dataset, please share in comments.

The process of guessing essentially constructs a decision tree, which is equivalent to make the Huffman encoding for all substrings of $$$A$$$. What makes things difficult is that there can be $$$\mathcal{O}(n^2)$$$ distinct substrings, so firstly we need to reduce the number of different initial states. Note that we only care about the number of the occurrences rather than what it is, and we know the maximal number is at most $$$n$$$, so if we can categorize substrings by their frequency, we may simulate the Huffman tree's construction quickly.

There are several approaches to count all the frequency of substrings in linear time. One approach is to build the suffix array through SA-IS algorithm, and then build the compressed suffix tree from this suffix array. Counting on the suffix tree is easy. However, due to the character set size, suffix automaton in space complexity $$$\mathcal{O}(n \Sigma)$$$ may fall down.

After counting, let's try to calculate the cost of building the Huffman tree in linear time. In this process, we need to merge two states with the lowest frequency into a new state repeatedly until there remains only one state. Note that the number of new state's occurrences is equal to the sum of the old two.

Denote $$$c_i$$$ as the number of states that occur $$$i$$$ times $$$(i = 1, 2, \ldots, n)$$$. For the states with the number of occurrences $$$\leq n$$$, we can speed up the consecutive same actions at once, for example, merge at most $$$\frac{c_{i}}{2}$$$ pairs of states that occur $$$i$$$ times. For the states with the number of occurrences $$$> n$$$, we can conclude the number of such states $$$< \frac{n}{2}$$$, as $$$\sum_{i}{(i \cdot c_i)}$$$ is always equal to $$$\frac{n (n + 1)}{2}$$$. We can use a first-in-first-out queue to maintain and merge these states so that this part is finished linearly.

The above explication also shows that you don't have to discuss the occurrences in cases, but only utilize the trick of a queue, or two queues, to implement. By the way, it seems this idea has occurred in 700D - Huffman Coding on Segment, created by GlebsHP and Endagorion, however, few people were able to take advantage of it.

When talking about data structures of suffices, we usually refer to suffix array, suffix tree and suffix automaton.

More constantly, we build suffix array by prefix doubling with radix sort in time complexity $$$\mathcal{O}(n \log n)$$$, and build suffix automaton or suffix tree in time complexity $$$\mathcal{O}(n C)$$$ or $$$\mathcal{O}(n \log \Sigma)$$$, where $$$C$$$ is the constant caused by cache miss, as the space complexity is a bit large, $$$\mathcal{O}(n \Sigma)$$$. In usual, we don't care about $$$C$$$, because $$$\Sigma$$$ is fairly small, like the size of the classical Latin alphabet, $$$26$$$.

Sometimes, problems require more efficiency to build some of them offline. In this case, we may have to build suffix array linearly and transform between any two of these structures. The transform is easy, for example, suffix array with LCP array can help construct the suffix tree, and suffix links of suffix automaton forms the suffix tree of reversed string. The linear construction for suffix array can be DC3 or SA-IS.

This is a classic problem of Pólya enumeration theorem, which is similar to Dodecahedron -- Petrozavodsk Winter Camp 2008, Ural SU Contest. Both are not hard after applying this theorem.

By applying that, we can only focus on the number of ways to set colors for orbits meeting the coloring conditions. For a situation in which every $$$d$$$ faces should have the same color, we can count $$$dp(i, j)$$$ as the number of ways such that the first $$$i$$$ colors have been used to color $$$j$$$ faces without breaking any condition.

There are only $$$4$$$ types of equivalence classes, so the time complexity is $$$\mathcal{O}(4 F^2 n)$$$, where $$$F = 60$$$ is the number of faces.

By the way, Pólya enumeration theorem requires division. In order to do it, and do it only once, in modulo $$$p$$$, you can calculate the other parts in modulo $$$|G| \cdot p$$$, where $$$|G| = 60$$$ is the total number of equivalence classes, and then divide it by $$$|G|$$$ directly. During that process, you should be careful with $$$64$$$-bit integer overflow.

The number of polyhedral rotation group is quite small. For example, chiral tetrahedral symmetry of order $$$12$$$ is the rotation group of regular tetrahedron, chiral octahedral symmetry of order $$$24$$$ is the rotation group of cube and octahedron, and chiral icosahedral symmetry of order $$$60$$$ is the rotation group of icosahedron and dodecahedron. Once we want to solve a problem concerning the isomorphism of 3D rotation, we can try to apply the above groups.

Let's first take a look at an easier version, where only binary operators $$$+$$$, $$$-$$$ are permitted. In this case, we can ignore parentheses by expanding them. Then, we can regard each operator as a sign of the variable behind it and the sign of the first variable is always positive, which can help us ignore the order of variables. In that way, we can conclude the number of different expressions is $$$(2^n - 1)$$$, as each sign must be either positive or negative, and we only need to make at least one positive sign.

Based on the above version, we can get a similar conclusion in case that only $$$*$$$, $$$/$$$ are permitted. But when at least three binary operators are permitted, things become more complex. Now let's discuss the case that $$$+$$$, $$$*$$$, $$$/$$$ (and with parentheses) are permitted, because to solve the original problem, we have to solve this task first.

In this case, parentheses cannot be expanded easily, but we can split the expression into priority levels. In each level, only $$$+$$$ is permitted or only $$$*$$$, $$$/$$$ are permitted. Each expression in a level $$$k$$$ is regarded as a single variable, or several expressions in the level $$$(k - 1)$$$ joined by operators in the level $$$k$$$.

We split expressions in this way so that we can better understand and ignore the order of an expression's successors. Also, the operators in the ancestor level cannot affect the successor levels. Hence, we can design a somewhat slow DP to count. Let $$$f(n)$$$ be the number expressions having $$$n$$$ variables such that its successors, if exists, is joined by $$$+$$$, and let $$$g(n)$$$ be the same for $$$*$$$, $$$/$$$. We have

where $$${n \choose x_1, x_2, \ldots, x_k}$$$ means $$$\frac{n!}{x_1! x_2! \ldots x_k!}$$$.

The transition is to enumerate $$$k$$$ unordered successors with their number of variables and relabel these $$$n$$$ variables, however, it's easy to understand but not easy to implement, so let's take a look at their exponential generating function.

Define that $$$F(x) = \sum_{n \geq 1}{\frac{f(n) x^n}{n!}}$$$, $$$G(x) = \sum_{n \geq 1}{\frac{g(n) x^n}{n!}}$$$. We have

where $$$\exp(A) = \sum_{k \geq 0}{\frac{A^k}{k!}}$$$.

We can calculte $$$\exp(A)$$$ based on a fact that $$$B = \exp(A) \Leftrightarrow B' = A' \exp(A) = A' B$$$. Together with that, we can desgin a DP to maintain the first $$$n$$$ terms of $$$F(x)$$$, $$$G(x)$$$, $$$\exp(F(x))$$$, $$$\exp(2 F(x))$$$, $$$\exp(G(x))$$$, in time complexity $$$\mathcal{O}(n^2)$$$. But if you are familiar with divide and conquer optimization with fast convolution in modulo integers, you can speed the process into $$$\mathcal{O}(n \log^2 n)$$$. The optimization is mentioned in the last paragraph of the tutorial for 438E - The Child and Binary Tree, created by vfleaking. By the way, I've tried to apply the Newton-Iteration like approach, but I failed. If anyone comes up with a better solution, please share in comments.

Finally, let's focus on the original problem. The minus operator in a level can influence operators in the successor levels which may lead to duplicated counting, for example, $$$a + b / (c - d)$$$ and $$$a - b / (d - c)$$$ are equivalent, but if we keep the aforementioned counting approach, we will count them twice. It's not difficult to observe that if we regard an expression and its opposite (i.e. the expression such that their sum is zero) are equivalent, the counting will work. The transition is like

But there still exists a corner case that an expression's opposite may be invalid. In that case, the minus operator must not be involved in the expression, and how to count that has already been discussed. Therefore, the answer is twice the number of expressions that ignore the sign, minus the number of expressions that ignore the minus operator.

During the contest, I've made a trial. Before starting, I uploaded the first $$$300$$$ terms to OEIS, when there is no formula about this problem. Then, when I was randomly checking teams' submissions, I found about ten teams who had submitted the table of these terms.

I don't know what to say, but only hope the sport of programming competition won't be banned at some time in the future.

Hints are categorized by the number of accepted teams.