我们发现，直接算一个连通块非常的困难。这个时候可以尝试容斥。我们发现至少一个的特别好算：划分至少\(i\)个连通块的答案记为\(g(i)\)。\(g(i)\)比较好算，可以考虑 DFS 枚举出每一个点所在的连通块根，然后把连通情况放入线性基中，如果线性基插入失败，那么说明当前的情况不能被表示出，且该状态符合划分，那么计入小答案\(tot\)，最后对答案的贡献就是：\(2^{tot}\)。
现在考虑如何用\(g(i)\)算恰好\(i\)个连通块的答案\(f(i)\)。考虑搞下容斥系数，使得\(f(i)\)只被计算一次：
\[ \sum_{i = 1}^n \begin{Bmatrix} n \\ i \end{Bmatrix} coefficient(i) = [n = 1] \]
打表出来就是：
\[ coefficient(i) = (-1)^{i – 1} (i – 1)! \]
考虑超级暴力，设计状态\(dp[k][i][j]\)为走了\(k\)步处于\((i, j)\)的答案：
\[ dp[k][i][j] = mp[i][j] + \max \begin{cases} dp[k – 1][i – 1][j] \\ dp[k – 1][i + 1][j] \\ dp[k – 1][i][j + 1] \\ dp[k – 1][i][j – 1] \end{cases} \]
由于本人分治很菜，所以就来刷分治题了。
先思考 50 分\(O(n^2)\)的做法。记录每一个位置的原始值、变化后的最大值、变化后的最小值，然后发现如果一个位置\(i\)对后面的位置\(j\)有贡献当且仅当：
\[a_i < minVal_j \ (1) \\ maxVal_i < a_j \ (2) \]
所以这就相当于一个二位偏序的题目，有两个限制。我们可以用整体二分，在做完左区间之后，左区间按原来的值进行排序，而右区间按最小值进行排序，即可满足第一个条件；第二个条件可以用线段树来搞，搞两个指针来比较大小，然后用线段树来统计答案即可。非常好写。
这道题真的是令人窒息，也告诉了我比赛的时候上 QQ 是一个非常坏的习惯。
这道题 60 分做法非常之显然：相同体积的物品归为一种物品，且价值为同体积内最大的价值。这样就可以把物品数量压到 100 个以内。
但是这样是通过不了全部分数的，而且全部分数的容量非常之大，所以正常的 DP 优化是行不通的。做完上面的压缩之后，可以考虑做一些贪心进行优化。接下来我会详细的介绍这个贪心策略：
LCT (Link Cut Tree) 是一种维护树链的灵活的数据结构。与线段树不同的是，LCT 一般使用 Splay 这种非常优雅、灵活的数据结构来维护树链。因为 LCT 支持动态增边、删边，所以很多题目就可以打破一些限制进行求解。
真难。
简单来讲，题目要求满足\(\{x_i \mod m \in [1, m – 1]\}\)的\(k\)元组个数。我们可以先把\(x_i\)全部模上一个\(m\)，然后令\(A = \sum_{i = 1}^k (x_i \mod m)\)（注意，\(A\)并没有被整体取模，只是各项余数之和），可知\(A \mod m = n \mod m\)，且\(A\)的上限就是\(A = k(m – 1)\)（各项上限）。
我们做了这样一个设置之后，问题就可以转换为：对于每一个不同的\(A\)，满足\(A \mod m = n \mod m\)且\(A = \sum_{i = 1}^k (x_i \mod m), \forall i, x_i \in [1, m – 1]\)的\(k\)元组方案数。首先，我们可以先枚举每一个\(A\)来缩小问题的范围，根据\(A\)所满足的条件，可以这样遍历\(i\)来获得每一个\(A\)：