2021 CCPC 广州站
题目链接
一些记录
第一次参加CCPC~
Day0
热身赛。
T1是ICPC网络赛第二场原题。
T2简单模拟。
T3是个奇怪（没给数据范围）的计算几何。
第14min的时候切完了前两题。然后听到队友说了个三分套三分，就上去写了。很快写完交了一发，TLE，发现是三分次数太多，调小三分次数后变成了WA。
想着精度有可能不够，然后把第二个三分变成了 $O(1)$，并改了一个错误后，结果还是WA。
然后一直想办法调，造了几组极限数据，发现会被几乎平行的情况给卡掉。
一直到比赛结束也没有过，发现鸿蒙队交了将近50发，也没过。
晚上困得要死，10点没到就去睡觉啦。
Day1
7点15起了床。突然想起昨天忘记给机器调Python了。
于是随便吃了三个包子，就去到小机房，把Python给下载了。
比赛开始前手机的前置摄像头突然用不了了，但是电脑里面的二维码也已经没了，没有办法拍照。
于是采用了手机拍手机的策略，在开始前4min搞定了。
先开了H，发现是个构造，然后复杂地分了好多类，WA了三发之后在39min过了。
然后看完了K题，觉得挺可做的。接着看到队友在讨论I，突然觉得是个找规律题，于是我花了2min敲了个暴力，发现输出 $6\times 2^{n-3}$ 就好了，然后在49min的时候过了I。
接下来的C一直WA，WA了三发之后发现读错题了。。原来项链是个环状的结构。。然后改了之后也一直WA。
于是我去想有点思路的K。发现只要先容斥一下，把大于等于改成小于，这样就可以枚举lcm，从而枚举gcd了，然后之后就变成选定 $[1,m]$ 内的 $n$ 个数，问gcd=i,lcm=j的方案数了。这个也可以容斥做。
在封榜前大概0.5h开始写，写着写着发现第二个容斥复杂度太大过不去，想了想发现这个容斥可以分开做。
然后再随便想了想第一个容斥，发现用个莫反就可以做了。
于是在封榜前写完，交了一发，发现又T了。
试了一个极限数据，发现大概要用4s。将n的快速幂预处理后，WA了一发，在237min过了K。
接着去推F，搞来搞去完全不知道 $\sum_{i=1}^n \prod_{i\neq j}\frac{1+f_i-f_if_j}{f_i-f_j}$ 有何意义的时候，抬头一看，发现C被队友改了以后过了。。。通过手算F发现，$n=3$ 的答案竟然是 $2$，然后打了个表发现，这个式子竟然与 $f$ 没有关系。。。于是在280min的时候把F也过了。
封榜结束后的40min连过3题，直接让我们队从铁牌区飞到了金牌区。。。
23个Au，5题末尾，排在第22，倒数第二个Au。
颁奖Ag的时候看到没有我们，还是挺激动的哈哈哈。
这题出的太奇怪了。尤其是F这种逆推回去然后出成题的。。。还有0.5s时限的C，都不知在卡些什么。所以说总体体验一般。
Anyway，大学的第一场XCPC就还算圆满啦。
下星期的威海加油~
题解
A. Math Ball
题意
给定 $n$ 个多项式 $F_j(x)=\sum_{i=0}i^{c_j}x_i$。
求 $\prod_{j=1}^n F_j(x)$ 的前 $W$ 项系数和。
$W\le 10^{18},n,\sum c_j\le 10^5$。
题解
对于幂次比较小的，可以考虑将幂用第二类斯特林数展开转成下降幂：
$i^c=\sum_{j=1}^c\begin{Bmatrix}
c\
j
\end{Bmatrix}i^{\underline{j}}$，
那么有：
$$F_j(x)=\sum_{i=0}\sum_{j=1}^{c}\begin{Bmatrix}
c\
j
\end{Bmatrix}j!\binom{i}{j}x^i=\sum_{j=1}^c\begin{Bmatrix}
c\
j
\end{Bmatrix}j!\sum_{i=0}\binom{i}{j}x^i\=\sum_{j=1}^c\begin{Bmatrix}
c\
j
\end{Bmatrix}j!\frac{(1-x)^{c-j}x^j}{(1-x)^{c+1}}$$
答案就是 $[x^W]\frac{\prod_{k=1}^n(\sum_{j=1}^{c_k}S_2(c_k,j)j!(1-x)^{c_k-j}x^j)}{(1-x)^{\sum (c_k+1)}+1}$
对于分子中连乘的每一项，是一个 $c_k$ 次多项式，将 $(1-x)^{c_k-j}$ 通过二项式定理暴力展开，并预处理一行第二类斯特林数后，使用一次卷积即可算出。
设分子为 $F(x)$，$s=\sum_{k=1}^n(c_k+1)$。
则答案为 ：$[x^W]\frac{F}{(1-x)^{s+1}}$，根据 $\frac{1}{(1-x)^{s+1}}$ 的组合意义，答案相当于 $F$ 的某个系数乘上组合数之和。
将组合数转成下降幂除以一个阶乘的形式计算即可。
时间复杂度 $O(n\log ^2n)$。
C. Necklace
题意
给定一个长度为 $n$ 的环形的项链，上面有 $m$ 个特殊点，现在用 $m$ 段区间恰好覆盖这个项链，使得每个区间中有且只有一个项链。问这些区间的长度的最大值最小是多少。
$m\le 10^6,n\le 10^{18}$。
题解
显然二分，重点在判断上。
找到长度最小的那个区间的右端点，考虑转一圈后是否可行，如果是无法覆盖到最后一个，那么一定不行；如果是无法覆盖整个 $n$，那么将起点改为由此时到达最右的端点+1开始，再转一圈，如果此时不行，那么就一定不行。
时间复杂度 $O(m\log n)$。
F. Cactus
题意
设 $f_n$ 表示总点数为 $n$ 的，允许重边的，有标号的连通仙人掌的个数。
求 $\sum_{i=1}^n \prod_{i\neq j}\frac{1+f_i-f_if_j}{f_i-f_j}$ 对 $998244353$ 取模后的结果。
$n\le 3\times 10^5$。
题解
这玩意儿竟然跟 $f_i$ 无关。。。
答案即为 $fib_n$。
关于证明，它鸽了。
G. Slope
题意
给定 $n$ 个点 $(x_i,y_i)$，横坐标互不相同。
$m$ 次询问一个二维平面中平行于坐标轴的矩形，问在矩形内的点中 $\frac{|x_i-x_j|}{|y_i-y_j|}$ 的最小值。
$n\le 7000,m\le 7\times 10^5$。
题解
其实这题并不难啊。。
只考虑横坐标，那么就是一个简单的莫队。
再考虑纵坐标，最小值只有可能在相邻的纵坐标中取得，那么用线段树维护最小值，合并的时候记录临界的点即可。
莫队分块大小取 $\frac{n^2}{m}$，时间复杂度 $O(n\sqrt{m}\log n)$。
H. Three Integers
题意
给定 $a,b,c$，求出一组 $x,y,z$，满足 $x\bmod y=a,y\bmod z=b,z\bmod x=c$，或判定无解。
题解
不妨设 $a\geq b\geq c$。
当 $abc\neq 0$ 时，若 $a=b=c$ 则无解，否则， $(x,y,z)=(a,a+c+b,a+c)$ 为一组可行解。
当 $abc=0$ 时，若 $a=b=c=0$，则 $(1,1,1)$ 为一组解；若 $b=c=0$，则 $(a,2a,2a)$ 为一组解；若 $c=0$，则 $(a,2a+b,2a)$ 为一组解。
时间复杂度 $O(1)$。
I. Pudding Store
题意
多次询问有多少个长度为 $n$ 的排列的前缀和的两倍均为为 $i$ 的倍数。
$n\le 10^9$。
题解
打表可知，当 $n\le 2$ 时答案为 $n$，否则为 $6\times 2^{n-3}$ 。
K. Magus Night
题意
问所有长度为 $n$ 的数组 $a$ 的 $\prod_{i=1}^n a_i$ 的和，满足 $1\le a_i \le m$ 且 $a_i$ 为整数，$\gcd(a_1,a_2,\cdots,a_n)\le q$，且 $\text{lcm}(a_1,a_2,\cdots,a_n)\geq p$。
$1\le n \le 10^9,1\le p,q\le m\le 2\times 10^5$。
题解
$\text{lcm}$ 一定为 $\gcd$ 的倍数。因此，我们可以枚举 $\text{lcm}$ 后，枚举其因数作为 $\gcd$。
但是题目里是 $\text{lcm}(a_1,a_2,\cdots,a_n)\geq p$，不好枚举，于是容斥一下，撇开 $\text{lcm}$ 的限制后，统计出 $\gcd(a_1,a_2,\cdots,a_n)\le q$ 的答案，那么就可以转换为枚举一个较小的 $\text{lcm}$ 了。
枚举lcm,gcd是 $O(m\log m)$ 的，然后根据乘法分配律，分开质因子去统计答案。对于每个质因子的答案，也可以容斥去做。
需要预处理某些数的 $n$ 次幂。
第一个容斥中，统计 $\gcd(a_1,a_2,\cdots,a_n)\le q$ 的答案使用简单莫反即可。
时间复杂度应该是两个 log 的。