脚本宝典收集整理的这篇文章主要介绍了The 2020 ICPC Asia Macau Regional Contest 题解，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
设加速器序列为 (a_1, a_2, cdots, a_n)，那么考虑把题目里的式子展开：(a_n+a_na_{n-1}+a_na_{n-1}a_{n-2}+cdots + prod_{i=1}^n a_i)。
我们把它一项项考虑。对于第 (k) 项，如果枚举过所有 (n!) 种情况，那就是对下标集合 ({1, 2, 3, cdots, n-1, n}) 选出一个长为 (k) 的排列 (a_{p_1}, a_{p_2}, cdots, a_{p_n})。而每个 (p) 都有若干次贡献，但我们最终要求期望，这个东西最终要被除掉，所有可以不考虑。
简化一下式子，就是：
分子上的东西实际上就是 ([x^k]prod_{i=1}^n (1+a_ix))。答案就是 (forall kin {1, 2, cdots, n}) 求个和。分治 FFT 即可，复杂度 (O(nlog^2 n))。
从这个角度看问题：每次我们钦定一对点 (u, v) 不在同一个 club 里。不难发现一定是在所有关系 ((i, j)) 二元组中找其中若干个 (w_ioplus w_j) 最小的，越多越好，直到找到一个发现关系冲突了为止。之所以要找最小的，是因为如果我们跳过了一些小的，那这些小的就不得不成为答案（参考 MEX）。
再观察，发现我们只要使这些关系构成一颗树（最小异或生成树）即可，原因是我们不必等到出现冲突，也不用管是不是没有成树就出现了冲突，答案方案就已经固定。对于一个固定的方案，我们可以通过 01-Trie 求解答案。
而求异或最小生成树是个套路问题了。每次按某一位（从高位到低位枚举）分治，然后借助 01-Trie 找到联立两个点集的最小边即可。总复杂度 (O(nlog^2 w))。
考虑最省顶点的方式，就是构造 ((d+1)) 个点的完全图，用以应付一个 department。最后只需要考虑 (c=1) 的情况了。
考虑如下构造：将 (n) 个点排成环，每个点向两侧相邻的 (lfloor d/2rfloor) 个点连边。如果 (d) 为奇数就向对面再连边。如果 (n) 是奇数使得没有对面的点，那说明无解，因为这样整张图的度数和就是奇数了。
注意特判 (d=0,1)，以及点数不够用的情况（(c(d+1)>n)）。
一开始有一个比较怪的想法，就是每次 push back 后，从后往前暴力按必胜必败态定理更新，再加一个如果对当前考虑的点不起作用就跳过。但是感觉不好操作也没啥前途就先弃了。
其实有更优秀的解法：记 (s_i) 为 (i) 这个位置先手是否必胜。
考虑一个关键性质：对于出现超过一次的 (x)，选取 (A_i=A_j=x) 且 (i<j) 的一对 ((i,j))。讨论一下 (s_j)：
也就是说，如果询问一个 (k)，满足 (A_k) 不是最后一次出现的，那么 (s_k=1)。如果是最后一次出现的，我们可以暴力维护 dp 去应付这种询问。对一个点暴力 dp 复杂度是 (O(log A))，每次 push back 要对所有 (A) 都做一遍（这里注意顺序）。
总复杂度 (O(nAlog A))。
（口胡，暂时还没写）转化询问：对于一个询问 (s, k)，找到一个最长的区间 ([s,t])，满足区间中出现次数超过一次的元素的，出现次数减一，的和，不超过 (k)。然后对于所有区间中出现次数超过一次的元素，找出其中权值最大的求和；对其他的元素直接求和。计算最终结果。
如果“出现次数”、“区间”相关的题目做多了，不难反应到，定义一个 (textit{last}_i) 表示位置 (i) 的元素在序列中上一次出现的位置（第一次出现则 (textit{last}_i = 0)）。那么上述的 (t) 就是最大的一个整数，满足 (sum_{i=s}^t [textit{last}_i < s] le k)。
抓住 (kle 10)，即 (k) 很小这个特点。考虑我们可以暴力找出所有 (last_i<s) 的这些 (i)，具体的，建立线段树，维护区间 (textit{last}) 的最小值，然后一次线段树上二分即可找到一个 (textit{last}_i < s) 的最近的 (i)。如此往复 (O(klog n)) 可以完成所有这样位置的搜寻。
然后我们实现统计答案：求出 ([s, t]) 的权值和，然后减掉出现次数超过一次的，但不是最大的元素的权值。这里要减去的只有 (O(k)) 个。
最后修改是非常简单的事情，复杂度 (O(mklog n))。（瞟了眼题解，好像胡对了？）
从排列的角度考虑问题：对于一个排列 (p)，有多少合法的 (a)？显然是 (n!)。而所有 (n!) 种排列都对应 (n!) 种 (a)，那么答案就是 ((n!)^2/n^n)。
然而我傻掉了，使用找规律通过了此题。
以上是脚本宝典为你收集整理的The 2020 ICPC Asia Macau Regional Contest 题解全部内容，希望文章能够帮你解决The 2020 ICPC Asia Macau Regional Contest 题解所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。