2020-牛客多校-5

坑

I 数学构造题

想这类题的时候不能太过于从有限的角度去考虑无穷的角度，如果用有限的面积拓展到无限的面积，那么最多大概也就1/2, 5/9的情况，这不是最优的。应该用无限的观点去尝试构造，考虑一个金块最多可以贡献出4个信标，一个炼丹炉最多也可以贡献4个信标，并且认为这一个金块和一个炼丹炉都能在平均的意义下满足4个信标的放置条件，那么最好的情况就是4/6 = 2/3。

下面给出一种构造方式，斜着放两串1，2、3交替填充在凹槽里即可。

E 置换与大数LCM

求出每个环长度的LCM即可，得用高精度，手写大数/JAVA

因为要找所有的序列，可以通过若干次的置换成为有序序列，那么就等价于将有序序列[1, 2, ...,n]通过反向置换可以得到的不同序列的个数，转化完后显然就是求所有环长度的LCM了。

D LIS

仔细观察题目给的两种操作后发现就是将一个数移动到另一个位置会花费一次代价，要使得移动次数最少使得成为一个有序数列，那么只要找所有起点开始LIS最长是多少即可。复杂度$O(n^2logn)$

B 异或MST

容易发现，不管之前是否有进行过删边加边操作，连接两个点的边的权值不变。

那么dfs一遍原图，用根节点到当前节点路径上所有边权的异或和作为点权，跑完全图的异或MST即可。

异或MST已经更新到模版template中，速度飞快，常数较小$O(nloglog)$

总体算法思想是boruvka算法，利用切分定理进行多路增广，这样保证最多只要增广logn次即可合并到一个联通块。而在异或图中找增广则可以On枚举某一个联通块中所有节点，利用01trie在其余节点中Olog的找最小的边权进行相连。

虽然可以朴素地在trie中删去当前联通块中所有点、查询最短边、加回之前联通块中所有点（常数巨大）来处理，但是在牛客会TLE掉，真的非常慢。。

一种很快的办法是在01Trie上做暴力搜索。可以料想，因为要使得异或后边权最小，所以在01trie上一定是子树的孩子之间会配对到最优的连边情况。因而递归处理，当处理完某个节点的左子树和右子树后，暴力枚举一边的子树，在另一端用01trie的性质贪心地找最短的边，从而完成左右子树的合并。可以动态维护vector，也可以比较漂亮地（而且速度快一倍orz）利用循环来划分左右子树，具体代码参见template。

这道题虽然有个异或MST的知识点，但是能想到最开始的结论其实也不容易qaq。

C 生成函数&构造

根据生成函数理论，对于函数$f(x, y) = (x^1 + x^2 + …)^k (y^1+y^2+…)^k$，展开式中单项式$x^ny^m$的系数就是满足$\sum a_i = n, \sum b_i=m$的所有可能的序列个数。我们将序列拆分成k组$(x^1+x^2…)(y^1+y^2+…)$来看，假设该序列对答案贡献出了单项式$x^iy^j$，那么此时其系数贡献显然只有1，题目要求每一对$a_i, b_i$都要贡献出$min(a_i, b_i)$次，那么我们考虑构造出一种办法，可以让每一组$(x^1+x^2…)(y^1+y^2+…)$都能贡献出$min(i, j)$次$x^iy^j$个单项式。可以采取如下精妙的办法：将其修改为$(x^1+x^2…)(y^1+y^2+…)(1+xy+x^2y^2+…)$，这样在原先序列中的$x^iy^j, x^{i-1}y^{j-1},x^{i-2}y^{j-2},…$都会通过$(1+xy+x^2y^2+…)$中的某一项映射到$x^iy^j$,而序列${x^iy^j,x^{i-1}y^{k-1}, …x^0y^{j-i}}$的个数就是$min(i, j)$，这样，这$min(i, j)$个单项式都会贡献出1，总共贡献就是$min(i,j)$。

将所有的项叠加起来即可得到最终的结果.。

最终要求的积式$\prod min(a_i, b_i) $的值就是$(x^1 + x^2 + …)^k (y^1+y^2+…)^k(1+xy+x^2y^2+…)^k$中$x^ny^m$的系数。

根据组合公式，易知其结果为$\sum_{i=0}^{min(n-k, m-k)}(^{i+k-1}{k-1})(^{n-i-1}{k-1})(^{m-i-1}_{k-1})$

预处理一下$C(n,k-1)$即可，复杂度$O(Tn)$