[BZOJ-3160]万径人踪灭

Description

给你一个只含a，b的字符串，让你选取子序列使得：

给出n个数q[i]，给出F[j]的定义如下：
F[j] = sigma(q[i] q[j] / (i - j) ^ 2) (i < j) - sigma(q[i] q[j] / (i - j) ^ 2) (i > j)
令E[i] = F[i] / q[i]，求E[i]。

求C[k] = sigma(A[i] * B[i - k])，其中 k <= i < n。
n的范围是1e5。

给你2个高精度数，求这两个数的乘积。

有时候我们需要将两个多项式乘起来，如果我们采用类似高精度乘法的算法，那么时间复杂度是O(n ^ 2)的。
那么我们有没有更加优秀的时间复杂度呢？
答案是有的。我们可以用FFT来完成多项式乘法的任务，时间复杂度是O(n * logn)的。

给你一张n个点m条边的无向图，有两个点s和t。
询问从s到t的路径中，最大边权与最小边权的比值最小是多少。

给你n样物品，每个物品可以有两个属性a，b。
你要给每个物品挑选一个属性，使得跳出的属性之组成的数列从1开始连续的数字个数最多。

给你一个01矩阵，你每次操作可以交换两行或者交换两列。
问你是否能得到一个矩阵使得矩阵的主对角线（左上角到右下角的连线）都为1。

如果一个图的点集可以分为两部分，且所有边的两个端点都在不同的部分中，则这个图是一个二分图。
有很多关于多选一的问题都可以建模成二分图来解决。
这里我们先讲关于二分图最大匹配的问题。