2019 年电子科技大学 ACM-ICPC 暑假前集训数学与几何专题解题报告

Posted on In

5/10/12

牺牲博弈论的微积分与大学物理保护法。

A. 韬哥哥抽卡

题目描述

求：

数据范围： 且保证 ， 为质数。

题解

因为指数可能很大，所以先考虑扩展欧拉定理，当 是质数时 ，然后代入 即可。

然后就单独考虑指数，就是怎么求 ，因为 是质数，那么 一定是一个偶数，那么肯定就不是质数了。观察到 比较小，所以考虑扩展 Lucas 定理直接求解，其实就是分解模数然后 CRT 合并上去。根据 可知每个因子只有一个，还好算了挺多。

最后一遍快速幂即可。

时间复杂度 ，空间复杂度 。

反正跑得贼快。

代码见这里

B. 别问，问就是 AK

题目描述

多次询问，设 ，求 。

数据范围：，且 为质数。

题解

对于这样带质数还恒等的一般考虑模数 的原根。记 的原根为 。

则存在唯一 使得 。

根据计数规则，有：，即 。

显然 ，其中 。

那么现在问题是有多少符合条件的 使得 。

设 ，则：

因为 是质数，那么小于 的所有数逆元一定存在，所以对于任意一个 ，都存在 个对应的 。

于是答案就变成了 ，代入和式并化简得到最终答案为：

对于后一个求和可以直接用等差数列求和公式求。

前一个求和枚举 ，可得：

预先求出 在 下的逆元统计答案即可。

时间复杂度 ，空间复杂度 。

实际上时间复杂度应该是一个 的东西，这个和杜教筛的时间复杂度类似但是比杜教筛快……但是我也不知道这个跑得为啥这么快……

原题来自：HDU 6051. If the starlight never fade

代码见这里

C. oy function

题目描述

多组询问，求：

数据范围：。

题解

看起来像 Möbius 反演，可以先看一下 H 题的题解。但是实际上不用……

还是考虑枚举 ：

记 ，那么：

对于前一个求和，利用数论分块即可解决。

时间复杂度 ，空间复杂度 。

代码见这里

D. 如果早知道 wf 题也会被 ak - 年度版

题目描述

已知三阶递推式 ，。给出一段连续的 ，问最小满足条件的 。保证有解。

数据范围：。

题解

因为这样的三阶递推式可以构造矩阵：

所以我们求的就是最小的 使得 ，其中：

然后利用 BSGS 求解即可。

令 ，则 ，这样就不用求逆矩阵了。最后返回的值改一下即可。

时间复杂度 ，空间复杂度 。

代码见这里

E. xzlnb 教你避铳

题目描述

期末了，牺牲博弈论的微积分与大学物理保护法

题解

F. xzlnb 教你胡牌

题目描述

期末了，牺牲博弈论的微积分与大学物理保护法

题解

G. 你怎么还没睡啊

题目描述

一共 个盒子 个球，盒子可以互相区分，球可以互相区分，其中一个球装在一个确定的盒子里，剩下的球可以任意放在任意的盒子里。求放后每个盒子都有球的概率。

数据范围：。

题解

因为有一个球已经确定了位置，高中学过这样的情况要分类讨论。

  • 如果这个球放的盒子里只有它一个球，剩下的情况就是 个可区分的盒子里放 个球，要求盒不为空；
  • 如果这个球放的盒子里还有其他球，剩下的情况就是 个可区分的盒子里放 个球，要求盒子不为空。

总情况就是往 个可以互相区分的盒子里放 个球，两者相除即为所求答案。

对于 个互不相同的盒子里放 个互不相同的球，盒子不允许为空的情况，方案数为 。 为第二类 Stirling 数。

对于 个互不相同的盒子里放 个互不相同的球，盒子允许为空的情况，方案数为 。

然后求第二类 Stirling 数有一个卷积式子：

这样就可以快速求出需要的第二类 Stirling 数了。

答案式子为：

时间复杂度 ，空间复杂度 。

代码见这里

H. world domination

题目描述

在三维空间坐标系中，求在 处能看到多少整点，并且整点点坐标的绝对值都小于等于 。

这里定义看到为这个点到原点的连线上没有其他点。

数据范围：。

题解

这个和 SDOI 2008 的「仪仗队」一题很相似，但是这里是对这道题的三维拓展。

还和 SPOJ VLATTICE 差不多，但是 SPOJ 那道题只需要算第一卦限和三个坐标面三个坐标轴上的值就行了。

我们考虑点坐标绝对值均大于等于 的情况，其中一个或两个为 的情况和均为 的情况，并考虑对称性，在各个卦限和四分之一坐标面上答案均相等，可以得到答案为：

最后的 为点坐标有两个为 和三个都等于 的总情况数，为 。

考虑 Möbius 反演，先对简单的二维情况推导。

构造一个函数 ，可以发现这个函数很有意思：

其实是我们对着 Möbius 反演干了一件很无聊的事情：这里 ，，观察到 ，因为任意正整数都有一个因子是 ，所以有以上结论。

那么我们要求的就变成了：

我们交换后一个的求和顺序，变成枚举因子的形式：

然后这个式子就可以在 的复杂度内求出了。

对于三维情况，有类似推导，可以得到：

同样做一下即可。

时间复杂度 ，空间复杂度 。

实际上对于 可以利用数论分块，枚举变化点来求值。但是线性筛就是 的也不是多组查询就不优化了。

据说还可以杜教筛做到 ，但是太鬼畜了（

代码见这里

I. 快去睡觉

题目描述

个盒子 个小球，多次询问四种把小球放进这些盒子使得盒子不空的方案数：

  • 小球可互相区分，盒子可互相区分；
  • 小球可互相区分，盒子不可互相区分；
  • 小球不可互相区分，盒子可互相区分；
  • 小球不可互相区分，盒子不可互相区分。

数据范围：。

题解

很显然的是，如果 ，那么一定会出现空盒子，所以先把这部分判掉。

对于小球可互相区分，盒子可互相区分的情况，这个和 G 是一样的，是第二类 Stirling 数乘一个阶乘。

对于小球可互相区分，盒子不可互相区分的情况，是第一种情况除以一个阶乘。

对于小球不可互相区分，盒子可互相区分的情况，显然插板法这个是高中题。

对于小球不可互相区分，盒子不可互相区分的情况，这个是一个类似 DP 的递推。

具体可以参考 HaHaTa 的博客 (Web Archive)。

于是我们先预处理一下第二类 Stirling 数，组合数，那个 DP 和阶乘，然后计算即可。

时间复杂度 ，空间复杂度 。

代码见这里

J. 白给的几何题 1

题目描述

求矩形面积并。

数据范围：。

题解

矩形面积并有经典的离散化后扫描线+线段树算法。用扫描线维护 轴区域，然后查询 轴上有多长有效长度，乘起来就是面积了。

原题来自：POJ 1151. Atlantis

时间复杂度 ，空间复杂度 。

代码见这里

K. 白给的几何题 2

题目描述

求平面最远点对。

数据范围：。

题解

平面最远点对一定在凸包上，所以求凸包上的最远点对就完事了。

如果数据是随机的，XJB 暴力的复杂度是对的，因为随机 个点的凸包大小是 级别的，暴力就是 。

但是不是随机的话，这样显然被卡，直接生成一个 个点的凸多边形随便卡，于是利用旋转卡壳就可以了。

对于平面最远点对在凸包上的证明，可以利用调整法证明，如果一个点不在凸包上，那么调整到凸包上一定会增大答案。实际上咋证我也不会。

时间复杂度 ，空间复杂度 。

代码见这里

L. 白给的几何题 3

题目描述

给定 个点，求能够覆盖这 个点的最小圆。

数据范围：。

题解

最小圆覆盖是一个神奇的东西，利用随机增量法，先打乱所有输入，枚举一个点 ，如果 不在当前圆内，就把它设成圆心，半径为 ，然后枚举第二个点 ，如果这个点不在圆内，就把答案圆设成以 为直径的圆，再枚举第三个点 ，如果这个点不在圆内，就把答案设成三角形 的外接圆。这样看起来是 的，但是实际上是期望 的，证明是通过进入循环的概率证明的。实际上怎么证我也不会。

时间复杂度 ，空间复杂度 。

代码见这里