# 【题解】2020牛客暑期多校训练营（第一场） 精

### B-Suffix Array

• Let C_i = min_{j > i and s_j = s_i} {j - i}
• The B-Suffix Array is equivalent to the suffix array of C_1 C_2 ... C_n
• Detailed proof can be found in “Parameterized Suffix Arrays for Binary Strings • ” http://www.stringology.org/event/2008/p08.html

### Infinite Tree

• First, compute the “virual tree” of {1!, 2!, ..., n!}
• Second, to compute the actual cost, use Segment Tree or Fenwick Tree.
• O(m log^2 m)

### Domino

• See “Distances in Domino Flip Graphs”

• The answer is b^T A^{-1} b, which can be proved by Lagrange Duality.
• All we need is to compute the inverse matrix of the matrix A.

### Counting Spanning Trees

• The number of spanning trees is prod_{i >= 2} deg(x_i) deg(y_i)
• Detailed proof can be found in “Enumerative properties of Ferrers graphs”
https://arxiv.org/pdf/0706.2918.pdf

### Infinite String Comparision

• Compare the string a^{infty} and b^{infty} directly
• By the Periodicity Lemma, if there is no mismatches in the first a + b - gcd(a, b) characters, the two string are identical

### BaXianGuoHai, GeXianShenTong

• For simplicity, we denote the multiplication as +, and exponentiation as *
• Precompute B_{i, j} = 2^ {W * j} * v_i
• To compute sum_{i, j} (sum e'{i, j} * 2^{W * j}) v_i
• = sum_x x sum
{i, j} [e'{i, j} = x] B{i, j} = sum_x x Q_x
• To compute sum_x x Q_x • = sum_x (sum_{y >= x} Q_y)
• The overall complexity is O(nm / W + 2^W) • Taking W = 16 yields a fast enough solution

### Minimum-cost Flow

• We denote the cost in a network with capacity c and flow f as cost(c, f).
• cost(c, 1) = cost(c * 1/c, 1 / c) * c = cost(1, 1 / c) * c
• For a network with unitary capacity, its cost grows linearly with the flow f, with at most O(m) pieces.
• Thus, we can compute O(m) pieces first, and query in O(log m) time.

### 1 or 2

• For an edge e=(x, y) where d_x = d_y = 2, add the following edges:
• (x, e) (x', e)
• (y, e') (y', e')
• (e, e')
• The problems is turned into to find a perfect matching in a general graph, which can be solved with Edmond's Algorithm.

### Easy Integration

• The value is (n!)^2 / (2n+1)!
• Detailed proof can be found in “Wallis' integrals”.
https://en.wikipedia.org/wiki/Wallis%27_integrals

# 近期热帖

• 回复(4) 发表于 今天 14:57:28
• 回复(1) 发表于 今天 16:20:44
• 回复(1) 发表于 今天 12:39:26
• 回复(0) 发表于 今天 10:40:57
• 回复(0) 发表于 2020-09-24 20:21:00
• 回复(0) 发表于 2020-09-24 20:09:28
• 回复(0) 发表于 2020-09-24 18:45:10

# 等你来战

• 报名截止时间：2020-09-25 22:00
• 报名截止时间：2020-09-28 23:55
• 报名截止时间：2020-09-26 18:00
• 报名截止时间：2020-10-03 21:30
• 报名截止时间：2020-10-04 21:30
• 报名截止时间：2020-10-09 22:00
• 报名截止时间：2020-10-17 22:00
• 报名截止时间：2020-10-17 22:00
• 报名截止时间：2020-10-20 22:00
• 报名截止时间：2020-10-20 22:00
• 报名截止时间：2020-10-25 17:00
• 报名截止时间：2020-10-31 17:00

# 热门推荐

• 扫描二维码，关注牛客网

• 下载牛客APP，随时随地刷题