解法
假的单调队列哦。
考虑将每个类别元素的下标记好,然后先把每个类别标号最小的放入 multiset,然后对答案进行更新:每次取出最大和最小值做差更新,然后把最小值的下标更新后重新扔进 multiset 中。如果 multiset 中所有的类别都已经枚举完毕,那么直接跳出循环进行输出即可。
假的单调队列哦。
考虑将每个类别元素的下标记好,然后先把每个类别标号最小的放入 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 序列的相关内容。接下来给出证明。
其实这道题是一道大水题。我们知道成立条件为\(x_l \text{ xor } x_{l+1} \dots x_{mid} = x_{mid+1} \text{ xor } x_{mid+2} \dots x_{r}\),然而这个运算可以直接移项:因为\(xor\)是自己本身的逆运算。然后为了保证\(r-l+1\)为偶数,我们只需要在 Trie 树末端维护奇偶计数即可。