前言
首先祝贺本次喜闻乐见的 COCR Cup 2025 比赛圆满结束！竞赛题目具体内容如下：
题目编号 题目名称 题目类型 主要考点 题目难度 预计通过率 A Easy 语法题 初中几何 入门\color{red}{\mathtt{入门}}入门 50%50\%50% B Word 算法题 模拟法 普及/提高−\color{yellow}{\mathtt{普及/提高−}}普及/提高− 15%15\%15% C Force 数学题 高中物理、三角函数 普及+/提高\color{green}{\mathtt{普及+/提高}}普及+/提高 5%5\%5% D Stone 数学题 Nim 博弈、位运算 普及+/提高\color{green}{\mathtt{普及+/提高}}普及+/提高
5%5\%5% E Farm 数据结构题 K-D Tree、平衡树 省选/NOI−\color{purple}{\mathtt{省选/NOI-}}省选/NOI− 0.1%0.1\%0.1% F Run 数学题 扩展 Lucas 定理 省选/NOI−\color{purple}{\mathtt{省选/NOI-}}省选/NOI− 0.1%0.1\%0.1% G Zombie 数学题 数位 DP、倍增 NOI/NOI+/CTSC\color{black}{\mathtt{NOI/NOI+/CTSC}}NOI/NOI+/CTSC <0.1%<0.1\%<0.1% H Square 数据结构题
树状数组、线段树、离散化 NOI/NOI+/CTSC\color{black}{\mathtt{NOI/NOI+/CTSC}}NOI/NOI+/CTSC <0.1%<0.1\%<0.1%
难度分布为：入门题 222 道（A/BA/BA/B），中档题 222 道（C/DC/DC/D），难题 444 道（E/F/G/HE/F/G/HE/F/G/H）。
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
A. EASY
SUBTASK 100 PT
根据简单计算可得，∠C=30∘\angle C=30^{\circ}∠C=30∘，30∘30^{\circ}30∘ 角所对的边是斜边的一半，可得：AC=2AB=N×2AC=2AB=N\times2AC=2AB=N×2
AC CODE
时间复杂度：O(1)O(1)O(1)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
B. WORD
SUBTASK 100 PT
根据题意模拟即可。本题难点在于字符串函数的使用，以下是本题需用到的函数：
* size()：得到字符串的长度
* erase()：删除字符串的指定区域
* insert()：在字符串指定区域插入内容
* empty()：判断字符串是否为空
* substr()：截取字符串的指定区域
AC CODE
时间复杂度：O(n)O(n)O(n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
C. FORCE
SUBTASK 100 PT
引入三角形法则：当两个向量首尾相接时，从第一个向量的起点指向第二个向量终点的向量，即为这两个向量的和向量。
解决问题的过程如下：
1. 先将每个力分解为水平（xxx 轴）和垂直（yyy 轴）分量：
* 水平分量：Fxi=fi×cos(xi×π180)F_{x_i} = f_i \times \cos(x_i \times \frac{\pi}{180})Fxi =fi ×cos(xi ×180π )
* 垂直分量：Fyi=fi×sin(xi×π180)F_{y_i} = f_i \times \sin(x_i \times \frac{\pi}{180})Fyi =fi ×sin(xi ×180π )
2. 合力计算：将所有水平分量相加得到总水平分量 FxF_xFx ，所有垂直分量相加得到总垂直分量 FyF_yFy 。合力大小 F=Fx2+Fy2F = \sqrt{F_x^2 + F_y^2}F=Fx2 +Fy2 。
方向计算：使用 θ=arctan2(Fy,Fx)\theta = \arctan2(F_y, F_x)θ=arctan2(Fy ,Fx ) 计算合力方向（弧度），然后转换为角度。如果结果为负，加 360°360°360° 使其在 [0,360)[0, 360)[0,360) 区间内。
AC CODE
时间复杂度：O(n)O(n)O(n)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
D. STONE
SUBTASK 100 PT
学过的同学一眼看出：这是Nim博弈。没错，这是一道很模板的 Nim 游戏。但是如果 FM 处于必败态时，第 aN+1a_{N+1}aN+1 堆石子数量应该是多少呢？
众所周知：0⊕1=10\oplus1=10⊕1=1，处于必败态的 FM Nim 和为 000，那么下一堆石子只需要 111 即可。
拓展：Nim 游戏的博弈图和状态。
如果将每个状态视为一个节点，再从每个状态向它的后继状态连边，我们就可以得到一个博弈状态图。
例如，如果节点 i,j,k{i,j,k}i,j,k 表示局面为 i,j,ki,j,ki,j,k 时的状态，则我们可以画出下面的博弈图（由于篇幅有限，故仅显示部分状态节点和部分边)：
定义必胜状态为先手必胜的状态，必败状态为先手必败的状态。
通过推理，我们可以得出下面三条定理：
* 定理 1：没有后继状态的状态是必败状态。
* 定理 2：一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。
* 定理 3：一个状态是必败状态当且仅当它的所有后继状态均为必胜状态。
对于定理 1，如果游戏进行不下去了，那么这个玩家就输掉了游戏。
对于定理 2，如果该状态至少有一个后继状态为必败状态，那么玩家可以通过操作到该必败状态；此时对手的状态为必败状态——对手必定是失败的，而相反地，自己就获得了胜利。
对于定理 3，如果不存在一个后继状态为必败状态，那么无论如何，玩家只能操作到必胜状态；此时对手的状态为必胜状态——对手必定是胜利的，自己就输掉了游戏。
如果博弈图是一个有向无环图，则通过这三个定理，我们可以在绘出博弈图的情况下用 O(N+M)O(N+M)O(N+M) 的时间（其中 NNN 为状态种数，MMM 为边数)得出每个状态是必胜状态还是必败状态。
AC CODE
时间复杂度：O(T×N)O(T \times N)O(T×N)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
E. FARM
SUBSTASK 20 PT
可以发现直接暴力时间复杂度为 O(N×M×Q)O(N\times M\times Q)O(N×M×Q)，TLE，剪枝（或记忆化搜索）即可。
SUBTASK 45 PT
考虑使用 vector\mathtt{vector}vector，每次查询时查找之前每次操作 111 播下的种子即可。
45 PT CODE
时间复杂度：O(Q2)O(Q^2)O(Q2)
备注：由于一些原因，对于特殊性质 B 依旧可以通过，因此应当正常得分 30 pt。
SUBTASK 10 PT（特殊性质 B 正解）
可以发现每次操作 111 中的 kkk 为 111，因此可以直接在每次查询时直接查询每个 111 操作并删除。
SUBTASK 100 PT
由于存在二维数区间点数问题，我们考虑 K-D Tree 或平衡树。以下为 K-D Tree 解法：
分析 222 种操作的处理：
* 播种操作：将种子信息（坐标 (x,y)(x,y)(x,y) 的成熟时间 ttt 为当前时间加 kkk）插入到 K-D Tree 中。
* 采摘操作：查询矩形区域内所有成熟时间 ≤\le≤ 当前时间的蔬菜，并标记为已采摘。
但是这样的时间复杂度极限下可能达到 O(Q2)O(Q^2)O(Q2)，我们考虑剪枝。
* 每个节点存储子树的最小或最大 (x,y)(x,y)(x,y) 坐标和时间信息，用于快速剪枝。
* 使用 lazy tag 表示蔬菜是否已被采摘。
* 在查询时，根据这些信息可以快速跳过不满足条件的子树。
这样我们的时间复杂度为 O(NN)O(N\sqrt N)O(NN )，大约为 8×1078\times10^78×107。
AC CODE
时间复杂度：O(NN)O(N\sqrt N)O(NN )
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
F. RUN
SUBTASK 10 PT
对于 10%10\%10% 的数据 n≤5×103n \le 5\times 10^3n≤5×103，直接代入公式暴力递推、枚举即可。
SUBTASK 40 PT
首先化简公式，引入杨辉三角（当然使用 Catalan 数亦可）：
11 11 2 11 3 3 1…1\\ 1\ 1\\ 1\ 2\ 1\\ 1\ 3\ 3\ 1\\ \ldots 11 11 2 11 3 3 1…
杨辉三角的实质是二项式系数的几何排列。若一个人从第一个 111 处走，只能向下或右下，走到该地的方案数。其组合数表示为：
Cnk=n!k!×(n−k)!C_n^k=\frac{n!}{k!\times(n-k)!} Cnk =k!×(n−k)!n!
容易将公式转换为：
∑k=0n(kn)2 mod p\sum_{k=0}^n(_k^n)^2\bmod p k=0∑n (kn )2modp
根据范德蒙德公式化简：
∑k=0n(kn)2 mod p=∑k=0n(n−kn)(kn) mod p\sum_{k=0}^n(_k^n)^2\bmod p\\ =\sum_{k=0}^n(_{n-k}^{n})(_k^n)\bmod p\\ k=0∑n (kn )2modp=k=0∑n (n−kn )(kn )modp
再根据二项式定理化简：
∑k=0n(n−kn)(kn) mod p=(n2n) mod p\sum_{k=0}^n(_{n-k}^{n})(_k^n)\bmod p\\ =(_n^{2n})\bmod p k=0∑n (n−kn )(kn )modp=(n2n )modp
拓展：实际上存在 Vandermonde 恒等式可直接得到：
∑k=0n(kn)2=(n2n)\sum_{k=0}^n(_k^n)^2=(_n^{2n}) k=0∑n (kn )2=(n2n )
两边同时 mod p\bmod pmodp，得：
∑k=0n(kn)2 mod p=(n2n) mod p\sum_{k=0}^n(_k^n)^2 \bmod p=(_n^{2n})\bmod p k=0∑n (kn )2modp=(n2n )modp
由于 p∈Primep \in \operatorname{Prime}p∈Prime，考虑使用 Lucas 定理：
(nk)≡(⌊k/p⌋⌊n/p⌋)(k mod pn mod p)(modp)(_n^k)\equiv(_{\lfloor k/p \rfloor}^{\lfloor n/p \rfloor})(_{k \bmod p}^{n \bmod p})\pmod p (nk )≡(⌊k/p⌋⌊n/p⌋ )(kmodpnmodp )(modp)
其中，当 n<kn<kn<k 时，二项式系数 (nk)(_n^k)(nk ) 规定为 000 。
递归求解即可。
40 PT CODE
时间复杂度：O(p+logpn)O(p+\log_p n)O(p+logp n)
SUBTASK 100 PT
请先阅读 40 pt 做法。
由于 Lucas 定理只能在 ppp 为质数的情况下使用，对于 100%100\%100% 的数据我们考虑扩展 Lucas 定理。
对于 ppp 是一般的合数的情形，只需要首先对它做素因数分解：
p=m1a1m2a2…msasp=m_1^{a_1}m_2^{a_2}\ldots m_s^{a_s} p=m1a1 m2a2 …msas
然后，分别计算出模 miaim_i^{a_i}miai 下组合数 (kn)(_k^n)(kn ) 的余数，就得到 sss 个同余方程：
{(kn)≡r1(modp1a1)(kn)≡r2(modp2a2)…(kn)≡rs(modpsas)\begin{equation} \begin{cases} (_k^n)\equiv r_1\pmod{p_1^{a_1}}\\ (_k^n)\equiv r_2\pmod{p_2^{a_2}}\\ \ldots\\ (_k^n)\equiv r_s\pmod{p_s^{a_s}} \end{cases} \end{equation} ⎩⎨⎧ (kn )≡r1 (modp1a1 )(kn )≡r2 (modp2a2 )…(kn )≡rs (modpsas )
引入中国剩余定理（CRT）：
{x≡a1(modn1)x≡a2(modn2)…x≡ak(modnk)\begin{equation} \begin{cases} x\equiv a_1\pmod{n_1}\\ x\equiv a_2\pmod{n_2}\\ \ldots\\ x\equiv a_k\pmod{n_k} \end{cases} \end{equation} ⎩⎨⎧ x≡a1 (modn1 )x≡a2 (modn2 )…x≡ak (modnk )
利用中国剩余定理（CRT）即可求出模 ppp 的余数。
AC CODE
时间复杂度：O(logn)O(\log n)O(logn)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
G. ZOMBIE
SUBTASK 6 PT
数据范围较小，直接枚举即可。
6 PT CODE
时间复杂度：O(T×N)O(T\times N)O(T×N)
SUBTASK 100 PT
采用倍增上数位 DP 的方法。
我们先看式子：
posnew=((pos+f(pos)) mod p)+1pos_{new}=((pos+f(pos)) \bmod p)+1 posnew =((pos+f(pos))modp)+1
省略 +1+1+1，得：
posnew=(pos+f(pos)) mod ppos_{new}=(pos+f(pos)) \bmod p posnew =(pos+f(pos))modp
我们发现每次增量不会超过 999，因此如果不看个位前面每次的增量不会超过 111。也就是说对于除个位之外的每一位我们都是一点点变化的，每次循环每个阶段我们都会经历。于是我们发现个位是特殊的，考虑单独处理。既然其他位置每个阶段都会经历，那我们不妨找到最特殊的阶段——全 000（尽管不会出现）。而前面的阶段位数对后面剩下的影响只需要记录最大数码即可。
于是我们考虑定义 dp1i,j,k,dp2i,j,kdp1_{i,j,k},dp2_{i,j,k}dp1i,j,k ,dp2i,j,k 分别表示 2∼i2\sim i2∼i 位均为 000，jjj 是 i+1i+1i+1 位及以上的最大数码，个位现在是 kkk 的状态下，我们想要给 i+1i+1i+1 位加 111，并且第一次回到 2∼i2\sim i2∼i 位均为 000 的状态后个位的值，和需要的步数。
我们发现 dp1i,j,k,dp2i,j,kdp1_{i,j,k},dp2_{i,j,k}dp1i,j,k ,dp2i,j,k 只需要由 dp1i−1,dp2i−1dp1_{i-1},dp2_{i-1}dp1i−1 ,dp2i−1 开始然后枚举 i−1i−1i−1 开始由 0→90\to 90→9 的变化即可转移。
接下来我们有 333 步。
1. 对于 mod m\bmod mmodm 的操作，我们先尝试将 AAA 变为 0∼90\sim 90∼9。先变到要跨过 mmm 之前，我们先用 dp1i,j,k,dp2i,j,kdp1_{i,j,k},dp2_{i,j,k}dp1i,j,k ,dp2i,j,k 从低位开始一步步加到 000 然后加到不能再加后，再从高位一步步向下加到不能再加。
2. 然后因为我们反复跨过 mmm 的次数可能很多，于是我们通过 dp1i,j,k,dp2i,j,kdp1_{i,j,k},dp2_{i,j,k}dp1i,j,k ,dp2i,j,k 预处理数组 fri,j,k,toi,j,kfr_{i,j,k},to_{i,j,k}fri,j,k ,toi,j,k 表示 0∼90\sim90∼9 中的数 jjj 跨过 m2im2^im2i 次后变成的 0→90\to90→9 中的哪一个，用多少步，然后我们就可以快速处理跨过 mmm 了。
3. 接下来我们不会再走一次超过 mmm 的了，于是我们又按 Step1Step 1Step1 中的方法，从低位开始一步步加到 000 然后加到不能再加后，再从高位一步步向下加到不能再加。
最后 +1+1+1 即可。
AC CODE
时间复杂度：O(T×logN)O(T\times\log N)O(T×logN)
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
H. SQUARE
SUBTASK 20 PT
不断枚举 333 个不同颜色的点，时间复杂度 O(N3)O(N^3)O(N3)。
SUBTASK 60 PT
按 xxx 递增枚举前两个点，那么第三个点的情况被这两个点的 yyy 坐标分为三部分，分别记录 xxx 的后缀这三部分的 x,(x+y),(x−y)x,(x+y),(x-y)x,(x+y),(x−y) 最大值即可快速计算，离散化使支持区间查询，这里因为 NNN 比较小可以暴力更新，时间复杂度 O(N2)O(N^2)O(N2)。在实现时考虑对颜色进行置换，复杂度为 O(N2×6)O(N^2 \times 6)O(N2×6)。
SUBTASK 100 PT
采用扫描线、二位数点。
由于 NNN 较大，暴力更新会超时，采用树状数组或线段树的解法更新。
经过分析可以发现三个点的位置可能是：
1. 两个点在矩形的邻边上且相对，一个点在矩形内部。（共存在 666 组置换，两个边上的点控制了四边的缩小）
2. 两个点在矩形的边上且相边相邻，一个点在矩形邻边上。（共存在 444 组置换，三个点控制了四边的缩小）
首先对于颜色进行排列置换，并对坐标进行四个象限的变换。这样我们可以从左到右钦定颜色加入的顺序。
经过前面的变换，我们按照 xxx 坐标升序，我们发现本质不同的三个点形态只有 yyy 递增，或者先增再减。
第一种可以直接开两个树状数组，把第一个点的 −x−y−x−y−x−y 扔进第一个树状数组，然后由第二点查询传递到第二颗树状数组（这里是为了保证有这样一个点处在中间）。
第二种情况我们可以按顺序加入前两个点，并用扫描线采用二位数点找出第三个点，在线段树上直接赋值（一个对后缀赋值，一个对前缀赋值，那么他们中间的点一定可以两个信息都接受到，并且合并这两个信息得到答案），最终在第三个点的 yyy 坐标处进行单点查询，需要把 xxx 的差加上，线段树里存的是 yyy 的差值和第一个点的 $。。
AC CODE
时间复杂度：O(NlogN×24)O(N \log N \times 24)O(NlogN×24)
