这道题其实就是高斯消元裸题。依照题意可以列出形如以下的方程：
\[ \sum_{i = 1}^n (x_a [i] – x_0 [i])^2 = c \]
其中\(c\)表示球的半径。一共有\(n+1\)个这样的方程，可以考虑上下相减消掉常数，这样就构造出了一个\(n\)个方程的方程组。最终方程组：
\[ \begin{cases} 2\sum_{i = 1}^n x_1[i] x_2[i] = \sum_{i = 1}^n (x_1[i])^2 – (x_2[i])^2 \\ 2\sum_{i = 1}^n x_2[i] x_3[i] = \sum_{i = 1}^n (x_2[i])^2 – (x_3[i])^2 \\ 2\sum_{i = 1}^n x_3[i] x_4[i] = \sum_{i = 1}^n (x_3[i])^2 – (x_4[i])^2 \\ \dots \end{cases} \]
扔到高斯消元里就搞定了。
这道题看数据范围可以联想到状压 \(DP\)。考虑设计一个状态：\(dp[S]\)代表女人的集合，其中集合长度\(|S|\)提供了另外一个信息，换句话说，\(dp[S]\)代表了考虑前\(|S|\)个男人对应的女人集合的转移个数。不难推出下面的式子：
\[ dp[S] = \sum_{(i, |S|) \in compatible} dp[S’], S’ \cup i = S \]
假的单调队列哦。
考虑将每个类别元素的下标记好，然后先把每个类别标号最小的放入 multiset，然后对答案进行更新：每次取出最大和最小值做差更新，然后把最小值的下标更新后重新扔进 multiset 中。如果 multiset 中所有的类别都已经枚举完毕，那么直接跳出循环进行输出即可。
这道题很有意思。首先搞一个 \(DP\) 来算出不同长度的不降子序列的个数，方程为：
\[ f[i, j] = \sum_{k < i, a_k \leq a_i} f[k, j – 1] \]
发现可以用树状数组优化，所以这里的复杂度为\(O(n^2 \log n)\)。设\(g[i] = \sum_{i = 1} f[i, n]\)，考虑对答案的贡献。对于一个\(i\)，有\(g[i] * (n – i)!\)种方案做变换，但是考虑这\((n – i)!\)中包含了提前变换完成的可能，也就是在我们从合法序列中删去了合法元素的可能，这样肯定是不行的。考虑进行容斥，贡献就是\(g[i](n-i)! – g[i+1](n – i – 1)!(i + 1)\)，表示在这些里选择\(i+1\)个合法元素的方案。
这道题是 DP + 容斥，正好是我不怎么会的类型。设状态\(f[i][j]\)为「考虑了前\(i\)个状态之后有\(j\)个颜色与原来一样的方案数（注意这里颜色不一样不是本质不同的）」。可以推出式子：
\[ dp[i][j] = \sum_{k = 0}^j dp[i – 1][j – k] {cnt[i] \choose k} \frac{cnt[i]!}{(cnt[i] – k)!} \]
结论 节点个数为\(n\)的无根标号树的个数为\(n^{n-2}\)。
这个结论在很多计数类题目中出现，要证明它首先需要了解 Prufer 序列的相关内容。接下来给出证明。