为了避免自己的账户泄露，建议不要在大机房中使用浏览器的“保存密码”功能！！
若认为自己的密码已经泄露，需要在修改密码后使用 登出所有活跃会话 功能，否则此前认证过的会话可能不会失效。
同时，为了避免权限组的题目泄露，hydd 大神指示各位 hy 的粉丝 使用强度较高的密码，请不要使用诸如 123456、114514、19260817、hyakcts、ilovechino 的弱口令。
FTP 所有账户已重置，请有 FTP 权限的群友查看系统消息获取最新的用户密码。对于 Archive 中一些公开的测试数据，建议大家转至 Google Drive 镜像进行下载。
不建议在博客中写模拟赛题的题解，如果需要写内部题的题解，一定注意添加权限。所有内部题目的讨论博客需要拥有 access-secret-blogs 权限与校内团队（目前有 $12,16,17,19,22$ 五个团队）权限才可以查看。
本公告的最终解释权归 hydd 所有。
因为一些原因去随便找了个爬虫爬了下来所有比赛名称。
下面是部分内容展示，完整版请见附件下载：
最后更新：2021.02.19，更新至比赛 id 25209
……
不写了
本帖所有内容均来自 Open Cup News 频道(https://t.me/opencup_ru), 若信息有冲突请以频道内容为准.
本帖所提及的发帖时间均指莫斯科时间 (UTC +3)
本帖最后更新于 06/03/2021 09:58 (UTC +3)
把所有形如$(a,ka)$的路径提出来，共有$O(n\log n)$条路径，后面将这种路径称为限制。
考虑答案路径如果要不合法，那么必然覆盖了至少一条完整的限制。
考虑覆盖限制$(u,v)$的路径$(a,b)$，设$dfn_x$表示$x$的$dfs$序，$end_x$表示$x$的子树中最大的$dfs$序，不妨设$dfn_u < dfn_v,dfn_a < dfn_b$。
第一种情况构成了$2$个矩形，第二种情况构成了$1$个矩形。
最终我们只要求出所有矩形的并然后取个反即可，扫描线$+$线段树，总复杂度$O(n\log^2 n)$。
观察一下可以发现，如果将同一行与同一列的$1$用边连起来，一种方案可以拆成很多个环，从这个方面入手。
设$f_n$表示$n\times n$矩阵的答案，我们枚举第一行所在环的大小，那么有递推式： $$f_n = \sum_{i = 2}^{n}A_i\cdot \binom{n}{i}\cdot \binom{n - 1}{i - 1}\cdot f_{n - i}$$
其中$A_i$表示$i\times i$的矩阵只有一个环的方案数，$\binom{n}{i}$表示选出$i$列，$\binom{n-1}{i-1}$表示选出除了第$1$行的剩下的$i-1$行。
先给出结论：$A_n = \frac{n!(n-1)!}{2}$，那么式子化成： $$f_n = \sum_{i = 2}^{n}\frac{i!(i-1)!}{2}\cdot \binom{n}{i}\cdot \binom{n - 1}{i - 1}\cdot f_{n - i}$$
将组合数拆开化简，得到： $$f_n = \frac{n!(n-1)!}{2}\sum_{i = 2}^{n}\frac{f_{n-i}}{((n-i)!)^2}$$
设$g_n = \frac{f_n}{(n!)^2}$，那么有： $$g_n = \frac{1}{2n}\sum_{i = 2}^{n}g_{n - i}$$
维护前缀和即可，复杂度$O(n)$。
现在考虑怎么证明$A_n = \frac{n!(n-1)!}{2}$。
先$n!$每行每列放一个$1$，设$p_i$表示第$i$行$1$的列编号。在$p_1$列放第二个$1$ 有$n-1$种方案，假设第二个$1$行号为$q_i$，那么接下来考虑$p_{q_i}$列，这列第二个$1$有$n-2$ 种放法，因为不能在此时返回第一行，再加上已有$2$个$1$的行不能再放$1$。接下来就是$n-3...$。除以二是因为这个过程的逆过程也被计算过了。
一眼费用流裸题，但是数据范围有点大，考虑动态维护流量。
设当前加入的点编号为$x$，因为深度是$O(\log n)$的，因此我们可以枚举$x$和$x$要到的点的LCA，对于当前LCA设为$g$，我们需要求出$g$往子树中走最小的代价使得可以流到一个还有剩余容量的点，设为$down_g$。注意子树中行走的代价可以根据每条边的流量正负来确定，因此要维护每条边的流量，其实就是手动维护网路流。我们需要求出$down_g+cost(x\rightarrow g)$中代价最小的那个，然后暴力维护每条边的流量即可。
复杂度$O(n\log n)$。
似乎 BZOJ 挂了以后就没有地方有 JSOI 2017 的题目了，于是上传了一下。
Enjoy!
这篇博客可以公开，就公开了。
$O(2^n)$ 枚举一下每个点染成什么颜色，然后从底向上 确定每一个点的权值， 如果所有点的权值都 $\geq 0$，则这是一组合法解，输出 POSSIBLE 否则继续做。
若没有合法解，则输出 IMPOSSIBLE。
时间复杂度 $O(n \cdot 2^n)$，期望得分 20 分。
可以考虑用树形 DP 来做。用 $f_{i,j}$ 表示 $i$ 的子树里和 $i$ 颜色不同的点的权值和为 $j$ 可不可行。 从底向上树形 DP 即可。
时间复杂度 $O(nv^3)$，期望得分 40 分。
因为这部分数据是一条链， 从底向上 dp 用 $f_{i,j}$ 表示是否存在一个合法方案满足上一个与 $i$ 颜色不同的节点是 $j$ 转移的时候， 对于 $i$ 号点 ，枚举上一个和它颜色相同的点 $k$ ，如果 $f_{i+1,k}=\mathsf{true}$ 且 $v_i\geq v_k$，那么这就是一种合法方案。
时间复杂度 $O(n^2)$，期望得分 20 分。
因为一个点的点权 $a$ 可以是 $\geq 0$ 的任意数，所以 $i$ 的子树里 (不包括 $i$)，和 $i$ 颜色相同的点的权值和要 $\leq v_i$ ，那么显然权值和要越小越好 。 那么可以参考算法 2 ，此时不需要两维 dp 了，只需要用 $f_i$ 表示 $i$ 的子树里和 $i$ 颜色不同的点的权值和的最小值。 因为这部分数据里一个点的儿子最多只有 $16$ 个，可以用 $2^{16}$ 枚举每个儿子 $j$ 和 $i$ 的颜色是否相同，若相同，则它的贡献是 $v_j$，否则贡献是 $f_j$，然后更新一下 $f_i$，从底向上 DP 。 时间复杂度 $O(n \cdot 2^{16})$，期望得分 20 分。
算法 4 已经很接近标算了。 只需要把算法 4 中 $2^16$ 的 0,1 枚举改成背包即可。 时间复杂度 $O(nv)$，期望得分 100 分。
https://en.wikipedia.org/wiki/Laplacian_matrix
Laplacian matrix for ''simple graphs''
Given a simple graph $G$ with $n$ vertices, its Laplacian matrix $L_{n \times n}$ is defined as
$$L = D - A$$
where $D$ is the degree matrix and $A$ is the adjacency matrix of the graph. Since $G$ is a simple graph, $A$ only contains 1s or 0s and its diagonal elements are all 0s.
In the case of directed graphs, either the indegree or outdegree might be used, depending on the application.
The elements of $L$ are given by
$$L_{i,j} := \begin{cases} \deg(v_i) & \mbox{if}\ i = j \\ -1 & \mbox{if}\ i \neq j\ \mbox{and}\ v_i \mbox{ is adjacent to } v_j \\ 0 & \mbox{otherwise} \end{cases} $$
where $\operatorname{deg}(v_i)$ is the degree of the vertex $i$.
Symmetric normalized Laplacian
The symmetric normalized Laplacian matrix is defined as:
$$L^\text{sym} := D^{-\frac{1}{2}} L D^{-\frac{1}{2}} = I - D^{-\frac{1}{2}} A D^{-\frac{1}{2}}$$
The elements of $L^\text{sym}$ are given by
$$L^\text{sym}_{i,j} := \begin{cases} 1 & \mbox{if } i = j \mbox{ and } \deg(v_i) \neq 0\\ -\frac{1}{\sqrt{\deg(v_i)\deg(v_j)}} & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j \\ 0 & \mbox{otherwise}. \end{cases}$$
Random walk normalized Laplacian
The random-walk normalized Laplacian matrix is defined as:
$$L^\text{rw} := D^{-1}L = I - D^{-1}A$$
The elements of $L^\text{rw}$ are given by $$L^\text{rw}_{i,j} := \begin{cases} 1 & \mbox{if } i = j \mbox{ and } \deg(v_i) \neq 0\\ -\frac{1}{\deg(v_i)} & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j \\ 0 & \mbox{otherwise}. \end{cases}$$
Generalized Laplacian
The generalized Laplacian $Q$ is defined as:
$$\begin{cases} Q_{i,j} < 0 & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is adjacent to } v_j\\ Q_{i,j} = 0 & \mbox{if } i \neq j \mbox{ and } v_i \mbox{ is not adjacent to } v_j \\ \mbox{any number} & \mbox{otherwise}. \end{cases}$$
Notice the ordinary Laplacian is a generalized Laplacian.
Adjugate matrix
The adjugate matrix $\operatorname{adj}(A)$ is the transpose of the matrix of the cofactors, that is, : $(\operatorname{adj}(A))_{ij} = (-1)^{i+j} M_{ji}.$
For every matrix, one has
$$(\det A) I = A\operatorname{adj}A = (\operatorname{adj}A)\,A. $$
Thus the adjugate matrix can be used for expressing the inverse of a [[nonsingular matrix]]:
$$A^{-1} = \frac 1{\det A}\operatorname{adj}A. $$
60 分做法：我们只需要枚举每条边，看看这条边出现在多少个树形图中，将这个值乘上边权，累加就是答案了。
如何求这条边在多少个树形图中呢？可以用补集转换，先求出树形图的总数；然后将这条边从图上删去，即在矩阵上加加减减，求出树形图个数，两者相减就是我们所要的值。
每次求一遍行列式，效率为 $O(mn^3)$
容易发现，求解的 $m$ 次行列式，每次只会修改矩阵某一行的两个值。运用简单的线性代数知识，可以求出基尔霍夫矩阵的伴随矩阵，就可以 $O(1)$ 计算行列式了！
至于伴随矩阵，可以求出逆矩阵，乘上行列式即可；至于逆矩阵， 和原矩阵一起消元就可以啦！$O(m+n^3)$
The lower bound on the number of groups if $k$ is odd is $\sum_{i=\frac{k+1}{2}}^k \binom ni$: all subsets of size at least $\frac{k+1}{2}$ have to belong to different groups. Similarly, if $k$ is even, the lower bound is $\frac{1}{2} \binom{n}{k/2} + \sum_{i=k/2+1}^k \binom ni$.
Note that $\binom ni \geq \binom {n}{k-i}$ when $i \geq k/2$. Hence, if we can match all subsets of size $i$ with subsets of size $k-i$ into non-intersecting pairs without common elements, we can achieve the lower bound.
Such a matching always exists when $i \ne k-i$, since the graph is bipartite and “regular” (not exactly, but all vertices in each part have equal degrees). When $k$ is even, the graph is not bipartite, but it turns out that forming $\left\lfloor \frac{1}{2}\binom{n}{k/2} \right\rfloor$ pairs of subsets of size $\frac k2$ is always possible for $n \leq 17$. Even though the graphs are huge, we can build them and try to find maximum matchings: using Kuhn’s algorithm for bipartite graphs, and using Edmonds’ blossom algorithm (or maybe Kuhn’s algorithm with hacks...) for non-bipartite graphs. Even though time complexity looks big, a greedy initialization already builds a huge part of the matching, and augmenting chains are very short on average too. You can try all possible test cases to make sure your solution is fast enough.
If you know a constructive way to build the matchings, or if you have a proof that an optimal matching of subsets of size $\frac k2$ for even $k$ always exists, please share!
简单题。