2020牛客暑期多校训练营（第一场）解题报告 | Bill Yang's Blog

# 路终会有尽头，但视野总能看到更远的地方。

0%

## A. B-Suffix Array

### 题目描述

The BB-function $B(t_1 t_2 \dots t_k) = b_1 b_2 \dots b_k$ of a string $t_1 t_2 \dots t_k$ is defined as follows.

• If there is an index $j < i$ where $t_j = t_i, b_i = \min_{1 \leq j < i, t_j = t_i}\{i - j\}$,
• Otherwise, $b_i = 0$.

Given a string $s_1 s_2 \dots s_n$ , sort its $n$ suffixes into increasing lexicographically order of the BB-function.

Formally, the task is to find a permutaion $p_1, p_2, \dots, p_n$ of $\{1, 2, \dots, n\}$ such that $B(s_{p_{i - 1}} \dots s_n) < B(s_{p_{i}} \dots s_n)$ holds for $i = 2, \dots, n$.

## D. Quadratic Form

### 题目描述

Bobo has a positive-definite $n \times n$ matrix $A$ and an $n$-dimension vector $b$. He would like to find $x_1, x_2, \dots, x_n$ where

• $x_1, x_2, \dots, x_n \in \mathbb{R}$,
• $\sum_{i = 1}^n \sum_{j = 1}^n A_{i, j} x_i x_j \leq 1$
• $\sum_{i = 1}^n b_i x_i$ is maximum.

It can be shown that $\left(\sum_{i = 1}^n b_i x_i\right)^2 = \frac{P}{Q}$ , which is rational.

Find the value of $P \cdot Q^{-1} \bmod 998244353$.

## E. Counting Spanning Trees

### 题目描述

Bobo has a bipartite graph with $(n + m)$ vertices $x_1, x_2, \dots, x_n$ and $y_1, y_2, \dots, y_m$.

The vertex $x_i$ is connected to the first $a_i$ vertices in $Y$, namely $y_1, \dots, y_{a_i}$.

Given $n, m, a_1, \dots, a_n$ and $\mathrm{mod}$, find the number of spanning trees of the graph modulo $\mathrm{mod}$.

## F. Infinite String Comparision

### 题目描述

For a string $x$, Bobo defines $x^\infty = x x x \dots$, which is $x$ repeats for infinite times, resulting in a string of infinite length.

Bobo has two strings $a$ and $b$. Find out the result comparing $a^\infty$ and $b^\infty$ in lexicographical order.

You can refer the wiki page for further information of Lexicographical Order.

## H. Minimum-cost Flow

### 题目描述

Bobo has a network of $n$ nodes and $m$ arcs. The $i$-th arc goes from the $a_i$-th node to the $b_i$-th node, with cost $c_i$.

Bobo also asks $q$ questions. The $i$-th question is specified by two integers $u_i$ and $v_i$, which is to ask the minimum cost to send one unit of flow from the $1$-th node to the $n$-th node, when all the edges have capacity $\frac{u_i}{v_i}$ (a fraction).

You can refer the wiki page for further information of Minimum-cost Flow.

## I. 1 or 2

### 题目描述

Bobo has a graph with $n$ vertices and $m$ edges where the $i$-th edge is between the vertices $a_i$ and $b_i$. Find out whether is possible for him to choose some of the edges such that the $i$-th vertex is incident with exactly $d_i$ edges.

### 题目分析

• $(x, e) (x’, e)$
• $(y, e’) (y’, e’)$
• $(e, e’)$

## J. Easy Integration

### 题目描述

Given $n$, find the value of $\int_{0}^1 (x - x^2)^n \mathrm{d} x$

It can be proved that the value is a rational number $\frac{p}{q}$.

Print the result as $(p \cdot q^{-1}) \bmod 998244353$.