算是个简单题吧。
首先列个暴力式子：
\[ \sum_G \sum_{i = 1}^n d_i^k \]
发现很不现实。我们考虑把点拆开来考虑，因为全集里面可以直接独立的来算。考虑某个点度数为 \(x\) 的方案数，就变成了：
\[ n \sum_{x = 0}^{n – 1} x^k f(x) \]
其中 \(f(x)\) 代表的是一个图某个点的度数为 \(x\) 的方案数。其实稍微思考下就知道，我们可以把这个点剥离出来，强制连边之后再生成一个图即可：
\[ \begin{aligned} f(x) &= {n – 1 \choose x} 2^{n – 1 \choose 2} \\ ans &= n \sum_{x = 0}^{n – 1} x^k {n – 1 \choose x} 2^{n – 1 \choose 2} \\ &= n2^{n – 1 \choose 2} \sum_{x = 0}^{n – 1} x^k {n – 1 \choose x} \end{aligned} \]
这个题有点 nb。
按道理来讲直接做第二问得要 \(\Theta(n^4)\) 的时间，而且看上去也没有什么搞头。我们考虑处理出所有的接壤位置 \( (x, y, c_a, c_y) \) 代表颜色为 \(c_x\) 、编号 \(x\) 的点和颜色为 \(c_y\) 、编号 \(y\) 的点接壤。这样的接壤位置只有 \(\Theta(n^2)\) 个，所以我们分类出来之后再用并查集搞即可。
一道比较板的上下界网络流。先考虑 \( red > blue \) 的情况，我们把所有点染成红色的然后再做个最大替换即可。我们考虑对每个点、每个横坐标、每个纵坐标做一个点，横坐标和源点、纵坐标和汇点的边需要大概算一下，得出流量范围 \(\frac{cnt_x}{2} \leq flow \leq \frac{d + cnt_x}{2}\)。得出这个范围之后就用板子套一下即可。
首先这题的 \(\Theta(n^3)\) 是很好写的，如果要写到 \(\Theta(n^2)\) 的分，我们可以观察到 DP 的过程其实是一个做后缀 min 的过程，所以优化完毕（当然也可以线性规划，但是很难写）。