A. Refreshed

If we don't take the shortest path from $$$s$$$ to $$$t$$$ but instead detour to some vertices to gain health, we must pass through an edge with both endpoints having a sum of weights greater than 0.

If we reach either vertex of such an edge, we can gain infinite health. We mark such vertices as infinite health vertices.

So, either we take the shortest path from $$$s$$$ to $$$t$$$, or we take the shortest path from $$$s$$$ to an infinite health vertex, gain infinite health, and then walk to $$$t$$$.

The second case can be maintained through up and down DP, which keeps track of the minimum health required to reach an infinite health vertex from each vertex.

The first case is to find the prefix minimum value of the path from $$$s$$$ to $$$t$$$. It is easy to see that the prefix minimum value is either the entire path or the entire path excluding the vertex $$$t$$$. Otherwise, there must be infinite health on the path, which can be handled by the second case. Of course, you can also use binary lifting directly.

The time complexity depends on LCA, and the optimal solution can be achieved in $$$O(n+k)$$$.

B. Ordered or Inverted

First, transform the problem into finding the answer for each $$$k=0,1,\cdots,n-1$$$ such that $$$\max_{i=1}^n|f(i)-g(i)|\leq k$$$.

Starting with an empty permutation, insert the numbers $$$1,2,\cdots,n$$$ one by one into a position in the current permutation (there are $$$i$$$ ways to insert $$$i$$$). This way, all possible permutations can be considered.

During the process, assume that $$$1,\cdots,i$$$ have been inserted, and now we want to insert $$$i+1$$$. If $$$i+1$$$ is inserted between the $$$p$$$-th and $$$(p+1)$$$-th numbers ($$$0\leq p\leq i$$$), the final number of ordered pairs corresponding to $$$i+1$$$ is $$$p$$$, and the number of inversions is $$$i-p$$$. We only need to ensure that $$$|p-(i-p)|\leq k$$$. Let the number of $$$p$$$ that satisfies the condition when inserting $$$i+1$$$ be $$$c(i)$$$, then we can get:

So, the problem is transformed into calculating $$$\prod_{i=0}^{n-1}c(i)=k!\prod_{i=k}^{n-1}\big(k+[i\equiv k\pmod 2]\big)$$$ for each $$$k$$$.

It is easy to calculate for a single $$$k$$$ in $$$O(\log n)$$$ time. The overall time complexity is $$$O(n\log n)$$$.

C. String

The number of occurrences of $$$T$$$ in $$$S_i = AB'$$$ is the sum of the number of occurrences of $$$T$$$ in $$$A$$$, the number of occurrences of $$$T$$$ in $$$B'$$$, and the number of occurrences of $$$T$$$ spanning across $$$A$$$ and $$$B'$$$.

The first two are easy to handle, so let's consider the last one.

A suffix of $$$T$$$ needs to match the prefix of $$$B'$$$, and the remaining prefix needs to match the suffix of $$$A$$$.

First, we can process all the suffixes of $$$T$$$ that match the prefix of $$$B'$$$, and then query how many of their remaining prefixes are suffixes of $$$A$$$.

We can build and solve this using KMP's fail tree.

The time complexity is $$$O(n\log n)$$$.

D. Annoying Permutation

We consider constructing two permutations as follows:

Then we can use $$$p_2^{k}\circ p_1\circ p_2^{n-k}$$$ to swap the positions of the $$$k$$$-th and $$$(k+1)$$$-th numbers without changing the positions of any other numbers. This is equivalent to being able to swap the positions of any two adjacent numbers, so we can perform bubble sort on the permutations, thus obtaining all $$$n!$$$ permutations. From this, we find that $$$k\leq2$$$.

The case of $$$k=0$$$ is easy to judge. Now we need to consider the case of $$$k=1$$$, that is, whether there exists a permutation $$$p$$$ such that for each $$$q_i$$$, there exists a $$$b_i$$$ such that $$$q_i=p^{b_i}$$$. Let the unit of the permutation be $$$e$$$, and the $$$i$$$-th prime number be $$$\mathfrak p_i$$$.

Definition Orbit, order: The orbit of a permutation $$$p$$$ is the set $$$\langle p\rangle:= \{ p^i:i\in\mathbb{N} \}$$$. The size of this set is called the order of $$$p$$$, denoted as $$$\operatorname{ord}p$$$.

We denote $$$a_i:=\operatorname{ord}q_i$$$, $$$A:=\operatorname{lcm}(a_1,\dots,a_m)$$$. Suppose there exists a permutation $$$p$$$ such that for each $$$q_i$$$, there exists a $$$b_i$$$ such that $$$q_i=p^{b_i}$$$.

Lemma: There must exist a permutation $$$p'$$$ with an order exactly equal to $$$A$$$, and for each $$$q_i$$$, there exists a $$$b'_i$$$ such that $$$q_i=p'^{b'_i}$$$.

Proof: Let $$$k:=\operatorname{ord}p/A$$$, consider $$$p':=p^k$$$. Since $$$q_i^{a_i}=e,p^{kA}=e$$$, we have $$$a_i=kA/\gcd(kA,b_i)$$$, that is, $$$\gcd(b_i,kA)=kA/a_i$$$. Since $$$A/a_i$$$ is an integer, $$$b_i$$$ must be a multiple of $$$k$$$, so let $$$b'_i:=b_i/k$$$, then $$$q_i=p'^{b'_i}$$$.

From now on, we consider that the order of $$$p$$$ is exactly $$$A$$$. In fact, we don't have to find $$$p$$$ exactly, we can find a $$$p^t$$$, as long as $$$t$$$ and $$$A$$$ are coprime. We randomly choose $$$0\leq k_i<A$$$, and let

Then

Lemma: $$$\gcd(b_1,b_2,...,b_m)=1$$$. When $$$k_i$$$ is uniformly random in $$$[0,A)$$$, $$$t=(\sum_{i=1}^mk_ib_i\bmod A)$$$, $$$t$$$ is uniformly random in $$$[0,A)$$$.

Proof: Consider decomposing $$$A$$$ into prime factors to get $$$A=\sum_{i=1}^\lambda\mathfrak p_i^{c_i}$$$. Consider each $$$b_i$$$ from the back, let

Then $$$\gcd(f_i,b_i)=1$$$, so

Therefore, $$$t\bmod f_i$$$ is uniformly random in $$$[0,f_i)$$$, and $$$\prod_{i=1}^{m}f_i=A$$$ and $$$\forall_{1\le i<j\le n}\gcd(f_i,f_j)=1$$$.

So we can obtain $$$t$$$ through the Chinese remainder theorem. Since $$$t\bmod f_i$$$ is uniformly random in $$$[0,f_i)$$$, $$$t$$$ is uniformly random in $$$[0,A)$$$.

Thus, the probability that the randomly chosen $$$t$$$ satisfies $$$t$$$ and $$$A$$$ being coprime is $$$\varphi(A)/A$$$. When $$$n\leq300$$$, the worst-case probability is given by

Now consider verifying whether $$$p^t$$$ is valid. For each $$$q_i$$$, we need to verify it in turn. For a transformation $$$x\to y$$$ in $$$q_i$$$, $$$x$$$ and $$$y$$$ should be in the same permutation cycle of $$$p^t$$$, with the cycle length denoted as $$$S$$$. We label each element of each permutation cycle of $$$p^t$$$ in turn, denoted as $$$d_j$$$. We must have,

So we can get a congruence system for $$$b_i$$$. If for each $$$q_i$$$, $$$b_i$$$ has a solution, it means that $$$p^t$$$ is the answer. We can repeat the random process above multiple times. When randomizing 100 times, the worst-case accuracy is as high as 99.99998%. In fact, randomizing 50 times is enough to pass the test data of this problem.

In summary, the algorithm has a time complexity of $$$O(nmc\log A)$$$, where $$$c$$$ is the number of random attempts. In practice, this complexity is not fully utilized.