「BZOJ 4788」[CERC2016]Bipartite Blanket
题目大意二分图点有点权，定义点集的权值为点权和，统计二分图中有多少个点集，满足被至少一个匹配覆盖。 $n,m \leq 20$题解首先你要知道一个叫做霍尔定理的东西：设 $G$ 中有一组匹配，一端恰好为组成 $X$ 的点的充分必要条件是： $X$ 中的任意 $k$ 个点至少与 $Y$ 中的 $k$ 个点相邻。（摘自百度百科） 这个告诉了我们如何判断一个点集是否能被一个匹配覆盖，但是暴力枚举+...
题目大意二分图点有点权，定义点集的权值为点权和，统计二分图中有多少个点集，满足被至少一个匹配覆盖。 $n,m \leq 20$题解首先你要知道一个叫做霍尔定理的东西：设 $G$ 中有一组匹配，一端恰好为组成 $X$ 的点的充分必要条件是： $X$ 中的任意 $k$ 个点至少与 $Y$ 中的 $k$ 个点相邻。（摘自百度百科） 这个告诉了我们如何判断一个点集是否能被一个匹配覆盖，但是暴力枚举+...
题目大意把 $n$ 个数分成 $k$ 个区间，每个区间的价值为区间内不同数字的个数，问价值和最大为多少。题解简单 dp：设 $f_{i,j}$ 表示前 $i$ 个数 分了 $j$ 段的价值和最大是多少。我们记 $cnt_{l,r}$ 表示 $[l,r]$ 的不同的数的数量，那么有转移朴素的转移是 $O(n^3)$ 的，我们观察这个式子，如果固定 $j$ ，我们用线段树维护 $f_k+cn...
题意：给你一个序列s，你把这个序列的所有不同排列按字典序排列后，求s的排名mod m 不保证 $m$ 是质数。 题解：我们记 $cnt_i$ 表示填到当前 $i$ 这个数还有多少个，不难发现题目要求的是： 显然后面的和式可以用树状数组轻松维护。 发现 $m$ 不一定是个质数，我们质因数分解后对于每一个 $p_i^{e_i}$ 分开做就好了。中间要将所有的数的 $p_i$ 因子都提取出来。（感...
题目链接 首先 $f_{[1\cdots k-1]} = 1$，所以发现每个 $f_x$ 都可以表示成 $f_k^e$ 的形式。 我们首先通过矩阵乘法算出来 $f_k^e = f_n$ 的解，然后就是解方程 然后因为 $g = 3$，用 BSGS 算出两项，最后用 exgcd 解出 $e$ 直接代入即可。 代码:/* * Author: RainAir * Time: 2019-07-...
B现在有一棵树 要求对于每个点 $x$ ,求所有点到他的链的最大点权之和 $n \leq 4 \times 10^5$题解：又是我不会的思博题。 这种题目我们可以首先考虑在链上的做法： 显然有一种基于分治的方法，但是很难扩展到树上。 所以我们考虑如果变成边权是不是好维护。。（ 我们考虑定义点 $i$ 和 $i+1$ 之间的边的边权是 $max\{a_{i},a_{i+1}\}...