【题解】牛客挑战赛37
A.牛牛与序列计数
找规律或者打表不难发现答案%5En%7D%7B16%7D)
。
那么当
为奇数时
,当为偶数时
。
推导的话这里给出一个生成函数的推到做法，对于红色和蓝色，不难发现生成函数都是
，对于黑色和白色，生成函数都是
。
两种都是经典的生成函数，分别为
和
。那么答案是%5E2(%5Cfrac%7Be%5Ex%20-%20e%5E%7B-x%7D%7D%7B2%7D)%5E2)
展开后
的系数，我们对这个式子化简后泰勒展开可以得到答案是
。
B.牛牛与组合数学
现在直接算出
不太靠谱，我们考虑用质数来随机测试。
我们可以取
个质数作为检测质数，然后每次去判定
是否等于
。我们对每个模数都去预处理之后再用
定理快速计算。只要通过一定次数的模数测试，我们就认为
。复杂度是)
。
不过由于数据范围等等一系列问题，这个题并没有达到期望的效果，不能算作一道好题。
C.牛牛要女装
观察这个递归，然后把他的搜索树画出来，显然发现是一棵二叉树，而且把
值当作这个点的权值的话，很容易可以发现，左子树的值肯定都比小，右子树的值肯定都比大。显然这是一棵
。
而这个
就是这个的中序遍历。因为满足当前点，左子树，右子树的遍历顺序。我们可以利用在二叉搜索树二分的方法，找到第m个值。
具体实现注意几个细节：
1.C++自带的)
向下取整的话，如果
很大，可能会有精度的误差。
2.如果递归的姿势不太好，可能需要手工栈来防止出现爆栈的情况。
3.1ull << 64是ub的，在某些编译器上可能跑不过。
D.牛牛与星辰
先考虑一下
的做法，一共有
个三角形。开三重循环去枚举所有情况，然后判断一下这三个点形成的三角形里面面积符合要求的个数。
上述做法相当于枚举一条线段，然后去查询有多少个点和这条线段形成的三角形的面积在
区间。那么现在的问题是如何对于每条线段都快速统计合法答案。
有一个经典做法是极角排序加旋转坐标轴，不过看上去写计算几何的选手并不多。首先我们把个点按照为第一关键字，
为第二关键字升序排，我们把这个序列定义为
。然后我们枚举排序之后的点
，对于所有的点)
，我们都可以得到一条向量
。
我们对于得到的%7D%7B2%7D)
个向量进行极角排序，那么在极角排序之后可以得到一系列有特别性质的向量序列。具体来说，当我们枚举到向量时，另外
个点在序列里面离向量的距离是有序的，那么对于这个有序序列，我们可以直接在上面二分得到合法答案。然后当离开这条向量到下一条向量时，我们只需要交换这条向量的两个端点在序列里面的位置，就能保证接下来的序列也满足对向量距离有序这个性质。复杂度是)
。
E.OJ用户管理系统
考虑到所维护的二叉树的编号满足大根堆的性质，而权值满足二叉搜索树的性质。在交换和
的权值后，我们先交换和
在二叉树上的位置，使得权值仍然满足二叉搜索树的性质。
此时如果和在二叉树上不是祖先关系，考虑到和的编号是连续的，编号仍然满足大根堆的性质。否则交换位置后是的父节点，需要对上旋一次使得编号满足大根堆的性质。
维护深度变化量之和时，由于二叉树的中序遍历始终按权值从小到大排列，因此我们可以按照二叉树的中序遍历建线段树或者树状数组维护答案。
F.牛牛喜欢看小姐姐
首先恰好求被
个小姐姐经过的点数可以通过容斥转化为至少被个小姐姐经过的点数。
步长为
的小姐姐可以经过所有标号为)
倍数的点,为了方便，下面就用表示)
。
问题等价于:
到
至少是个的倍数的数有多少个。
集合的并的大小显然可以容斥考虑，现在有
个集合，暴力容斥显然不可能，但是由于所有都为
的约数，所以任选个 的
也必定为的约数，所以从个集合中选任意集合的并只能得到))
个不同的集合,在
下最大只有
级别，所以可以考虑这些集合的容斥系数贡献。
由于每个集合的实际含义就是
到内有多少个数是的倍数，所以为了方便，每个集合可以用一个的约数来表示。
定义)
的容斥系数贡献为)
,那么即为从个数中选若干个数(不能是个)，使得恰好为，且选奇数个贡献为，偶数个贡献为
。定义)
为从个数中选若干个数(不能是个)，使得为的约数，且选奇数个贡献为，偶数个贡献为。由于所有数都是的约数，令
，每个质数看成是一个维度,则是
的约数等价于每一个维度的指数都比小,所以
是
的高维前缀和，只要能求出,就可以用高维前缀和的差分求出。
对于，选若干个数使得为的约数，等价于每个数都是的约数,假如个数中有
个是的约数，那么%3D%5Csum_%7Bi%3D1%7D%5EcC_c%5Ei(-1)%5E%7B(i-1)%7D)
,由二项式定理可知，若
，%3D1)
,否则 %3D0)
。
所以现在关注这个数中是约数的个数的情况，这个数本身就是通过从中任意选个数取生成，同理选个数的为的约数，那么这个数每个数都要是的约数，所以假如中是的约数的有
个,那么
,所以
时，
,否则
。
下面只需要求中是的约数的个数，经上面的分析可知，这是个高维前缀和。设最大因子个数为
,最大不同质因子个数为
,那么整体复杂度是)
.
查看13道真题和解析
