By contradiction, we can prove that for a connected 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 capacity 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 could figure out by adjusting that at most two of them should be cut, since there are at most two non-intersect paths between $$$s$$$ to $$$t$$$. In addition, if there are many cycles where some edges of each of them are cut, it can be known by adjusting and contradiction that only the edges of at most one cycle of them should be cut.

One observation is that if there is at least one edge in some cycle should be cut in the best solution of the minimum cut problem, there must be two edges in that cycle need to be cut, one of which is the edge with the smallest capacity in that cycle. Hence, we can remove the edge with the smallest capacity in each cycle and add its capacity to the other edges in the cycle, and the maximum flow between any two vertices will not change in value.

The modified graph forms a tree. If we add edges to an empty graph in descending order of its capacity, 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 edge of capacity $$$w$$$. Just maintain these sets of vertices by the disjoint set union, count in each set the number of vertices whose bit 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 may 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 searching and 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 and check. 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 the tree's centroid decomposition, in order to calculate $$$|S_u|$$$ online.

Since the restricted distances are the same, when $$$S_u$$$ and $$$S_v$$$ have a non-empty intersection, their intersection equals to the set of vertices whose distance to the middle point of the path between them 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 each edge of the tree.

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

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. It seems there are many problems similar to this one.

Though the data range is small, we should be careful calling functions like acos(x) when $$$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, they are equivalent by applying Dilworth's theorem.

We may be familiar to the case that $$$p_i = 2$$$ for all $$$i$$$, which is equal to find a maximal subset of the power set of some set $$$S$$$ such that none of the sets is a strict subset of another. Besides, the conclusion, also known as Sperner's theorem, is that the size of the maximal subset is equal to $$${|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 turn, 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. 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.

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 behavior, there was only one team achieving that.

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. Amazingly, during the contest, there are tremendous Chinese teams using this approach to pass, even though many of them don't understand it.

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. Time complexity is $$$\mathcal{O}(10^3 n)$$$.

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]$$$ $$$(i = 1, 2, \ldots, N)$$$ 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]$$$, 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 no matter $$$K$$$ is, the number of solution is always $$$2^{m (N - 1)}$$$.

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

Now 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 $$$x_i \in [0, R]$$$ or $$$x_i \in [0, L - 1]$$$. Then, let's take a look at the digit DP. We can record the sign caused by the inclusion-exclusion principle, and then boost the same transition 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 determine XOR value on this bit, and determine the lower bits by XOR equation. The only difference is due to the upper bounds of the higher bits, when we apply the inclusion-exclusion principle. Fortunately, their bitwise XOR sum differs only if the parity of the number of upper bounds that are $$$R$$$, so we can record the parity of their number, which is equivalent to the sign caused by the inclusion-exclusion principle, and implement easily.