【题解】牛客挑战赛33

A

发现数据范围比较小，所以直接暴力算就好了。
为了避免除法，可以两边都乘上。
其实可以证明只有在时两者相等，否则前者一定比后者大。

B

要在个之间插个，那么这个一定只能插在奇数位置上的后面。
那么一共有个位置可插，答案就是个非负整数加起来为的方案数，即。

C

枚举一下从上底面走到下底面经过了哪条底面的边，然后把侧面展开到和下底面在同一个平面里，然后起点终点的最短路径就是展开后的直线距离。
记得判断直线是否与枚举的边有交点。
然后就可以计算了。

D

定义数组，表示第个朋友吃的零食。
显然，的上界是，即。然后我们给出一种方案，可以构造出满足的所有。
首先，，，，然后从小到大枚举，将赋值成最小的没有选择过的数。这样，对于，，所以这是一种合法的方案。
通过简单的数学归纳法，我们可以证明，那么我们只需要再构造出，和的方案即可。
当时，。
当时，，，, 。
当且为奇数时，，，，)。
当且为偶数时，，，)。
这几种构造显然都是合法的。

E

我们设 为值域， 为选出的所有数都为 的倍数的方案数，经过简单的莫比乌斯反
演，答案就是 。
我们对于每个 求出可以重复选 个数的方案数，然后通过容斥就可以求出不能重复
选 个的方案数。我们设一个阈值 ，如果 ，那么我们使用快速沃尔什变换求 ，复
杂度为 。如果 ，我们用 ，复杂度为 。
如果我们设 ，那么复杂度为 。

F

把所有点的点权从小到大排序，之后可以假设第个点的点权为，设为答案大于的图的个数，我们求出了所有就求出了答案。 即为不存在一个连通块，其中所有点权都的图的个数。
可以使用容斥原理计算，枚举不交的个所有点权的连通块，答案就是要加上包含这个连通块的图的个数乘上。
设为所有点数为的简单无向图的权重之和，权重定义为：若这张图有个连通块，权重为。那么枚举的大小之和，即可得到。如果计算出了，那么一次卷积即可解决此题。
设为点数为的简单无向图的个数，为点数为的简单无向连通图的个数，把看作指数生成函数，可以得到，，那么。那么使用一次求逆即可求出，解决此题。