语雀题解，密码：gfli
COCR 系列竞赛往届题目：题单
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
繁杂の附魔：模拟
正解
我们只需判断 a÷2a\div2a÷2、b÷4b\div4b÷4 和 ccc 的结果最小值即可。
时间复杂度：O(T)O(T)O(T)
预计得分：100pts100pts100pts
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
烦人の建交：贪心
正解
贪心策略就是对于同一个亲戚，我们只需要选择时间最少的即可。在处理每个亲戚的时间时，我们可以用 vis 数组记录是否见到过。
时间复杂度：O(NlogN)O(N \log N)O(NlogN)
预计得分：120pts120pts120pts
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
石子の游戏：博弈论、DFS枚举
题意简述
输入 NNN 和 MMM 表示石子的数量和最多拿取的石子数，输出必胜方和可能出现的拿取方案。
赢家分析
这是一个经典的巴什博弈问题。根据其结论可得：
* 当 N mod (M+1)=0N \bmod (M+1) = 0Nmod(M+1)=0 时，先手必赢。
* 当 N mod (M+1)≠0N \bmod (M+1) \neq 0Nmod(M+1)=0 时，后手必赢。
由于当先手必胜时，一定会出 N mod (M+1)N\bmod (M+1)Nmod(M+1)，使得剩下的石子数量为 M+1M+1M+1 的倍数。
方案数分析
由于必输方可以随意拿取 111 到 MMM 个石子，所以影响方案数的因素是必输方的拿取方案。我们可以使用排列公式来解决，在排列时记录每种方式。
每一方的拿取方案
由于必胜方需要让自己拿到石子数量与上一轮对方拿的石子数量之和为 M+1M+1M+1，所以若不计入先手必胜情况中的先手率先拿取的石子数量，轮数为：N÷(M+1)N\div(M+1)N÷(M+1)。
正解
时间复杂度：O(MNM+1)O(M^{\frac{N}{M+1}})O(MM+1N )
预计得分：140pts140pts140pts
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
定点の轰炸：ST表、线段树
题意简述
题目描述了一个城市，城市中有 NNN 座房子，每座房子有一个高度 hih_ihi 。JW 的父亲需要执行 QQQ 次轰炸任务，每次任务给定一个区间 [l,r][l, r][l,r]，要求在这个区间内选择高度最高的房子进行轰炸。如果有多个房子高度相同，选择编号最小的那个。
解题思路
这个问题可以转化为一个经典的区间最大值查询问题。我们需要在给定的区间 [l,r][l, r][l,r] 内找到高度最大的房子，并返回其编号。由于 NNN 和 QQQ 都可能非常大 （N≤3×105N \leq 3 \times 10^5N≤3×105，Q≤106Q \leq 10^6Q≤106），我们需要一个高效的算法来处理这些查询。
方法选择
1. 暴力法：对于每个查询，遍历区间 [l,r][l, r][l,r]，找到最大值。这种方法的时间复杂度是 O(Q×N)O(Q \times N)O(Q×N)，显然无法通过。
2. 线段树：线段树可以处理区间查询和更新操作，时间复杂度为 O(logN)O(\log N)O(logN) 每次查询。对于 Q=106Q = 10^6Q=106 来说，总时间复杂度为 O(QlogN)O(Q \log N)O(QlogN)，可以通过。
3. ST表：ST表是一种用于解决静态区间最值查询的数据结构，预处理时间复杂度为 O(NlogN)O(N \log N)O(NlogN)，查询时间复杂度为 O(1)O(1)O(1)。对于 Q=106Q = 10^6Q=106 来说，总时间复杂度为 O(NlogN+Q)O(N \log N + Q)O(NlogN+Q)，也可以通过。
由于题目中房子高度是静态的（不会改变），ST表是一个非常适合的选择。
预处理
1. 定义：st[i][j]st[i][j]st[i][j] 表示从位置 iii 开始，长度为 2j2^j2j 的区间内的最大值的位置。
2. 初始化：对于每个 iii，st[i][0]=ist[i][0] = ist[i][0]=i，因为长度为 111 的区间最大值就是它自己。
3. 递推：对于每个 jjj，从 i=1i = 1i=1 到 i=n−2j+1i = n - 2^j + 1i=n−2j+1，比较 st[i][j−1]st[i][j-1]st[i][j−1] 和 st[i+2j−1][j−1]st[i + 2^{j-1}][j-1]st[i+2j−1][j−1] 所对应的值，取较大的那个。
查询
对于查询区间 [l,r][l, r][l,r]，我们可以找到一个 kkk，使得 2k≤r−l+1<2k+12^k \leq r - l + 1 < 2^{k+1}2k≤r−l+1<2k+1。然后比较 st[l][k]st[l][k]st[l][k] 和 st[r−2k+1][k]st[r - 2^k + 1][k]st[r−2k+1][k] 所对应的值，取较大的那个。
正解
时间复杂度：O(NlogN)O(N\log N)O(NlogN)
预计得分：160pts160pts160pts
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
重复の任务：线段树、背包DP、高精度
题意简述
一个任务系统，JW 需要完成一系列任务来获得“同祝”。每个任务都有一定的送祝福数量和收到“同祝”数量，且任务的完成会消耗一定的精力。JW 的精力是有限的，我们需要计算在精力用完前，JW 最多能收集到多少个“同祝”。
解题思路
本题具有很明显的背包dp和线段树特征与特性。
任务的计算
对于第 iii 个任务，f(i)f(i)f(i) 表示送祝福数量与收到“同祝”数量的和。
对于第 111 个任务，f(1)=a1+b1+max(a1,b1)f(1)=a_1+b_1+max(a_1,b_1)f(1)=a1 +b1 +max(a1 ,b1 )。
对于第 i(i≥2)i(i≥2)i(i≥2)，f(i)f(i)f(i) 的计算涉及到前 aia_iai 和 bib_ibi 个任务 f(j)f(j)f(j) 的和，以及这些任务中 f(j)f(j)f(j) 的最大值。
背包DP
本题的数据 kik_iki 的范围较大，所以需要使用优化。（题解采用二进制优化，也可选择单调队列优化）
正解
由于数据可能过大，这里使用高精度算法进行加和乘的操作。
时间复杂度：O(NlogN+N×w[0])O(N\log N+N\times w[0])O(NlogN+N×w[0])
预计得分：180pts180pts180pts
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
奇怪の公式：数论、素数筛、矩阵、欧拉定理
题意简述
给出 f(n,x,y)f(n,x,y)f(n,x,y)、gig_igi 、h(x)h(x)h(x) 的定义，求 h((gcd(gn,gx+y) mod 105)!)h((\gcd{(g_n,g_{x+y})} \bmod 10^5)!)h((gcd(gn ,gx+y )mod105)!) 的值。
公式化简
公式 1
fn,x,y=(∑0≤i,2∣inCni+∑i=0n(∑j=0nyjxn−jCnj)Cni)mod 109+7f_{n,x,y}=(\sum_{0 \le i,2|i}^{n}C_n^i + \sum_{i=0}^{n}(\sum_{j=0}^{n}y^jx^{n-j}C_n^j)C_n^i)\mod 10^9+7 fn,x,y =(0≤i,2∣i∑n Cni +i=0∑n (j=0∑n yjxn−jCnj )Cni )mod109+7
由引理
(x+y)n=∑i=0nyixn−iCni(x+y)^n=\sum_{i=0}^{n}y^ix^{n-i}C_n^i (x+y)n=i=0∑n yixn−iCni
带入 x=1,y=1x=1,y=1x=1,y=1 可得
∑0≤inCni=∑i=0n1i1n−iCni=(1+1)n=2n\sum_{0 \le i}^{n}C_n^i=\sum_{i=0}^{n}1^i1^{n-i}C_n^i=(1+1)^n=2^n 0≤i∑n Cni =i=0∑n 1i1n−iCni =(1+1)n=2n
同理，带入 x=1,y=−1x=1,y=-1x=1,y=−1 可得
(1+(−1))n=∑i=0n(−1)i1n−iCni=0=∑i=0n(−1)iCni=Cn0−Cn1+Cn2−Cn3+⋯+(−1)nCnn→Cn0+Cn2+⋯=Cn1+Cn3+Cn5+⋯→∑0≤i,2∣inCni=∑0≤i,2∣(i+1)nCni→2∑0≤i,2∣inCni=∑0≤inCni=2n→∑0≤i,2∣inCni=2n2=2n−1\begin{aligned} (1+(-1))^n \\ =\sum_{i=0}^{n}(-1)^i1^{n-i}C_n^i=0 \\ =\sum_{i=0}^n(-1)^iC_n^i \\
=C_n^0-C_n^1+C_n^2-C_n^3+\cdots+(-1)^nC_n^n \\ \to C_n^0+C_n^2+\cdots =C_n^1+C_n^3+C_n^5+\cdots \\ \to \sum_{0 \le i,2|i}^{n}C_n^i =\sum_{0 \le i,2|(i+1)}^{n}C_n^i \\ \to 2\sum_{0 \le i,2|i}^{n}C_n^i=\sum_{0 \le i}^{n}C_n^i=2^n \\ \to \sum_{0 \le i,2|i}^{n}C_n^i=\frac{2^n}{2}=2^{n-1}\end{aligned}
(1+(−1))n=i=0∑n (−1)i1n−iCni =0=i=0∑n (−1)iCni =Cn0 −Cn1 +Cn2 −Cn3 +⋯+(−1)nCnn →Cn0 +Cn2 +⋯=Cn1 +Cn3 +Cn5 +⋯→0≤i,2∣i∑n Cni =0≤i,2∣(i+1)∑n Cni →20≤i,2∣i∑n Cni =0≤i∑n Cni =2n→0≤i,2∣i∑n Cni =22n =2n−1
∑j=0nyjxn−jCnj=(x+y)n\sum_{j=0}^{n}y^jx^{n-j}C_n^j=(x+y)^n j=0∑n yjxn−jCnj =(x+y)n
∑i=0n(∑j=0nyjxn−jCnj)Cni=∑i=0n(x+y)nCni=(x+y)n2n\sum_{i=0}^{n}(\sum_{j=0}^{n}y^jx^{n-j}C_n^j)C_n^i=\sum_{i=0}^{n}(x+y)^nC_n^i=(x+y)^n2^n i=0∑n (j=0∑n yjxn−jCnj )Cni =i=0∑n (x+y)nCni =(x+y)n2n
fn,x,y=(∑0≤i,2∣inCni+∑i=0n(∑j=0nyjxn−jCnj)Cni)mod 109+7=(2n−1+2n(x+y)n)mod 109+7\begin{aligned} f_{n,x,y}=(\sum_{0 \le i,2|i}^{n}C_n^i + \sum_{i=0}^{n}(\sum_{j=0}^{n}y^jx^{n-j}C_n^j)C_n^i)\mod 10^9+7 \\=(2^{n-1}+2^n(x+y)^n) \mod 10^9+7 \end{aligned} fn,x,y =(0≤i,2∣i∑n Cni +i=0∑n (j=0∑n yjxn−jCnj
)Cni )mod109+7=(2n−1+2n(x+y)n)mod109+7
可用快速幂解决。
公式 2
gi={[i=1](i≤1)(fx,n,x+ygi−1+fy,x+y,ngi−2)mod 109+7(i>1)g_i = \begin{cases} [i = 1] & (i \leq 1) \\ (f_{x,n,x+y}g_{i - 1} + f_{y,x+y,n}g_{i - 2}) \mod 10^9+7& (i \gt 1) \end{cases} gi ={[i=1](fx,n,x+y gi−1 +fy,x+y,n gi−2 )mod109+7 (i≤1)(i>1)
定义p=fx,n,x+y,q=fy,x+y,np=f_{x,n,x+y},q=f_{y,x+y,n}p=fx,n,x+y ,q=fy,x+y,n
即：
gi={[i=1](i≤1)(pgi−1+qgi−2)mod 109+7(i>1)g_i = \begin{cases} [i = 1] & (i \leq 1) \\ (pg_{i - 1} + qg_{i - 2}) \mod 10^9+7& (i \gt 1) \end{cases} gi ={[i=1](pgi−1 +qgi−2 )mod109+7 (i≤1)(i>1)
容易发现这是斐波那契数列，其初始矩阵为：
[p1q0]\begin{bmatrix}p & 1 \\ q & 0\end{bmatrix} [pq 10 ]
可用矩阵快速幂解决。
公式 3
h(x)=∑d=1,x∣dxp∑1≤i∞i×(1−p)i−1(0<p<1)h(x)=\sum_{d=1,x|d}^{x}p\sum_{1 \le i}^{\infty}i \times (1-p)^{i-1}(0 < p <1) h(x)=d=1,x∣d∑x p1≤i∑∞ i×(1−p)i−1(0<p<1)
p∑1≤i∞i×p(1−p)i−1(0<p<1)=p×p∑1≤i∞i×(1−p)i−1\begin{aligned} p\sum_{1 \le i}^{\infty}i \times p(1-p)^{i-1}(0 < p <1) = p \times p\sum_{1 \le i}^{\infty}i \times (1-p)^{i-1} \end{aligned} p1≤i∑∞ i×p(1−p)i−1(0<p<1)=p×p1≤i∑∞ i×(1−p)i−1
定义
k=p∑1≤i∞i×(1−p)i−1=(1−p)0+2(1−p)1+⋅⋅⋅k−(1−p)k=1+2(1−p)+⋅⋅⋅−(1−p)−2(1−p)2−⋅⋅⋅=1+(1−p)+(1−p)2+⋅⋅⋅=∑0≤i∞(1−p)i=1⋅(1−(1−p)n)1−(1−p)(n→∞)=1−(1−p)np(n→∞)\begin{aligned} k=p\sum_{1 \le i}^{\infty}i \times (1-p)^{i-1}=(1-p)^0+2(1-p)^1+\cdot\cdot\cdot \\
k-(1-p)k=1+2(1-p)+\cdot\cdot\cdot-(1-p)-2(1-p)^2-\cdot\cdot\cdot \\ =1+(1-p)+(1-p)^2+\cdot\cdot\cdot \\ =\sum_{0 \le i}^{\infty}(1-p)^i \\ =\frac{1 \cdot(1-(1-p)^n)}{1-(1-p)}(n \to \infty) \\ = \frac{1-(1-p)^n}{p}(n \to \infty) \end{aligned} k=p1≤i∑∞
i×(1−p)i−1=(1−p)0+2(1−p)1+⋅⋅⋅k−(1−p)k=1+2(1−p)+⋅⋅⋅−(1−p)−2(1−p)2−⋅⋅⋅=1+(1−p)+(1−p)2+⋅⋅⋅=0≤i∑∞ (1−p)i=1−(1−p)1⋅(1−(1−p)n) (n→∞)=p1−(1−p)n (n→∞)
因为：
0<p<1→0<(1−p)<10<p<1 \to 0<(1-p)<1 0<p<1→0<(1−p)<1
所以：
(1−p)n(n→∞)=an(0<a<1)(n→∞)→0(1-p)^n(n \to \infty)=a^n(0<a<1)(n \to \infty) \to 0 (1−p)n(n→∞)=an(0<a<1)(n→∞)→0
k−(1−p)k=k−(k−pk)=k−k+pk=pk=∑0≤i∞(1−p)i=1p→k=1p2k-(1-p)k=k-(k-pk)=k-k+pk=pk=\sum_{0 \le i}^{\infty}(1-p)^i = \frac{1}{p} \to k=\frac{1}{p^2} k−(1−p)k=k−(k−pk)=k−k+pk=pk=0≤i∑∞ (1−p)i=p1 →k=p21
即：
p∑1≤i∞i×p(1−p)i−1(0<p<1)=p×k=p×1p2=1pp\sum_{1 \le i}^{\infty}i \times p(1-p)^{i-1}(0 < p <1) = p \times k =p \times \frac{1}{p^2}=\frac{1}{p} p1≤i∑∞ i×p(1−p)i−1(0<p<1)=p×k=p×p21 =p1
p×p∑1≤i∞i×(1−p)i−1=p×1p=1p \times p\sum_{1 \le i}^{\infty}i \times (1-p)^{i-1} =p \times \frac{1}{p}=1 p×p1≤i∑∞ i×(1−p)i−1=p×p1 =1
h(x)=∑d=1,x∣dxp∑1≤i∞i×(1−p)i−1(0<p<1)=∑d=1,x∣dxk2(k=1)=τ(x)h(x)=\sum_{d=1,x|d}^{x}p\sum_{1 \le i}^{\infty}i \times (1-p)^{i-1}(0 < p <1)=\sum_{d=1,x|d}^{x}k^2(k=1)=\tau{(x)} h(x)=d=1,x∣d∑x p1≤i∑∞ i×(1−p)i−1(0<p<1)=d=1,x∣d∑x k2(k=1)=τ(x)
由引理
τ(x)=∏p≤x(∑k=1∞(⌊xpk⌋)+1)(p∈Prime)\tau{(x)}=\prod_{p \le x} (\sum_{k=1}^{\infty}\left(\lfloor\dfrac{x}{p^k}\rfloor\right)+1)(p \in \text{Prime}) τ(x)=p≤x∏ (k=1∑∞ (⌊pkx ⌋)+1)(p∈Prime)
可得
h(x!)=∏p≤x!(∑k=1∞(⌊x!pk⌋)+1)(p∈Prime)h(x!)=\prod_{p \le x!} (\sum_{k=1}^{\infty}\left(\lfloor\dfrac{x!}{p^k}\rfloor\right)+1)(p \in \text{Prime}) h(x!)=p≤x!∏ (k=1∑∞ (⌊pkx! ⌋)+1)(p∈Prime)
计算结果
gcd(gn,gx+y)\gcd{(g_n,g_{x+y})} gcd(gn ,gx+y )
由引理得：
gcd(gn,gx+y)=ggcd(n,x+y)\gcd{(g_n,g_{x+y})}=g_{\gcd{(n,x+y)}} gcd(gn ,gx+y )=ggcd(n,x+y)
易得：
h((gcd(gn,gx+y)mod 105)!)→h(x!)(x=gcd(gn,gx+y)mod 105)h((\gcd{(g_n,g_{x+y})} \mod 10^5)!) \to h(x!)(x=\gcd{(g_n,g_{x+y})} \mod 10^5) h((gcd(gn ,gx+y )mod105)!)→h(x!)(x=gcd(gn ,gx+y )mod105)
xxx 可 O(log2(max(n,x+y)))O(log _2{(\max{(n,x+y)})})O(log2 (max(n,x+y))) 得出，h(x!)h(x!)h(x!) 可用素数筛 O(x)(x<105)O(x)(x < 10^5)O(x)(x<105)解决
正解
时间复杂度：O(Mod)O(Mod)O(Mod)，其中 Mod≤105Mod\le10^5Mod≤105
预计得分：200pts200pts200pts
