方程式
这个搜索好骚啊。
首先直接枚举 20 个数来搞初始根。假设我们拿到了\(s\)个根，那么我们还剩下\(n – s\)个，肯定是重根。所以我们考虑直接搜索剩下的\(n – s\)到底是哪个重根。这个复杂度就是\(\Theta(s^{n – s})\)。至于我们怎么验证解的正确性，就是这道题的精髓了：考虑把这组解写成零点式：
\[ \prod_{i = 1}^n (x – a_i) = 0 \]
我们做一个小的多项式乘法展开这个积式，然后与原式的系数进行对比即可。
这个搜索好骚啊。
首先直接枚举 20 个数来搞初始根。假设我们拿到了\(s\)个根，那么我们还剩下\(n – s\)个，肯定是重根。所以我们考虑直接搜索剩下的\(n – s\)到底是哪个重根。这个复杂度就是\(\Theta(s^{n – s})\)。至于我们怎么验证解的正确性，就是这道题的精髓了：考虑把这组解写成零点式：
\[ \prod_{i = 1}^n (x – a_i) = 0 \]
我们做一个小的多项式乘法展开这个积式，然后与原式的系数进行对比即可。
kal0rona 越来越 sb了。
看一眼复杂度，\(O(nm)\)级别的，考虑两个循环的 DP。分析整个题面之后发现，我们穿过边界时，当且仅当另一个连通块的权值比当前的大，否则便不会为了穿过边界而损失当前金块。所以，我们做一个 DP 一样的东西：因为发现每个格子只能走一遍，那么在每一列你只能选择一直向上走和一直向下走，所以这个 DP 便没了后效性，然后再处理连通块之间的连接判断就做完了。
首先，叶子结点为\(k\)时，整个完整的二叉树存在\(2k – 1\)个节点。我们设置一个 DP 来进行计数。
考虑设置状态\(dp[i][j]\)为当前树已有\(i\)个节点，且有当前加入的节点到根的路径有\(j\)单位长度。考虑以下转移：
\[ dp[i + 1][j + 1] += dp[i][j] \\ dp[i + 1][j – 1] += dp[i][j] \]
向新的节点加入统计数据：多了一个叶子结点，要么向左走，加深当前的路径；要么补上最后一个向左走的右节点。
然后就可以写代码了。
这道题是一道好题。
我们可以直接暴力 DP，考虑状态\(dp[i][j]\)为\(i\)个\(1\)与\(j\)个\(-1\)的答案。那么，我们可以从少一个\(1\)的情况和少一个\(-1\)的情况进行转移：
一定要思考，不能想当然。这句话是说给我听的。
把连通块连边，每一次 BFS 扩展就算做一次点击，然后\(O(n^2)\)确定路径长度，再按奇偶性判断就行了。