『RETOI』ROUND 2 全题解
T1 签到题 SIGN
题目大意
给定一个长不超过 10310^3103 的字符串，求这个字符串每一位的 ASCII 码值的乘积。
题目分析
根据题意，对于 100%100 \%100% 的数据而言，∣s∣≤103|s| \le 10^3∣s∣≤103，显然用 int128 也只能得到 505050 分，所以这时候就需要使用高精度乘法，先定义三个数组 a,b,ca,b,ca,b,c，初始时将 aaa 设为 111，接下来枚举字符串每一位上的字符，将其的 ASCII 码加入数组 bbb，用高精度将结果记录在 ccc 中，最后将 ccc 中的值复制回 aaa，以此类推，最终输出 aaa 数组中的数。
对于高精度乘法这里不在过多讲解，可自行参考 P1601。
CODE
T2 闰年 LEAP
题目分析
已知闰年的定义有以下几点：
* 能被 444 整除，而不能被 100100100 整除。
* 能直接被 400400400 整除。
这样问题就可以转换成：在 [l,r][l,r][l,r] 这个区间内有多少个正整数满足能被 444 整除而不能被 100100100 整除或者能直接被 400400400 整除。
已知 [1,n][1,n][1,n] 内有 ⌊n4⌋\lfloor\frac{n}{4} \rfloor⌊4n ⌋ 个数可以被 444 整除。同理，[1,n][1,n][1,n] 内有 ⌊n100⌋\lfloor\frac{n}{100} \rfloor⌊100n ⌋ 个数可以被 100100100 整除； [1,n][1,n][1,n] 内有 ⌊n400⌋\lfloor\frac{n}{400} \rfloor⌊400n ⌋ 个数可以被 400400400 整除。我们可以使用容斥原理，在 ⌊n4⌋\lfloor\frac{n}{4}\rfloor⌊4n ⌋ 中减去能被 100100100
整除的数的数量 ⌊n100⌋\lfloor\frac{n}{100}\rfloor⌊100n ⌋，再加上之前被错减掉的能被 400400400
整除的数的个数 ⌊n400⌋\lfloor\frac{n}{400}\rfloor⌊400n ⌋，这样我们可以得出在 [1,n][1,n][1,n] 之间的闰年个数为 ⌊n4⌋−⌊n100⌋+⌊n400⌋\lfloor\frac{n}{4}\rfloor-\lfloor\frac{n}{100}\rfloor+\lfloor\frac{n}{400}\rfloor⌊4n ⌋−⌊100n ⌋+⌊400n ⌋。
但是题目中要求求出 [l,r][l,r][l,r] 内闰年的数量。我们可以设 f(n)=⌊n4⌋−⌊n100⌋+⌊n400⌋f(n)=\lfloor\frac{n}{4}\rfloor-\lfloor\frac{n}{100}\rfloor+\lfloor\frac{n}{400}\rfloorf(n)=⌊4n ⌋−⌊100n ⌋+⌊400n ⌋，则 [l,r][l,r][l,r] 区间内闰年数量就是 [1,r][1,r][1,r] 内闰年数量减去 [1,l−1][1,l-1][1,l−1] 内闰年的数量，即 f(r)−f(l−1)f(r)-f(l-1)f(r)−f(l−1)。
CODE
T3 玉米树 TREEC
题目大意
给定一个字符串，两个入依次进行博弈（删字符），谁先删完谁赢。
题目分析
本场比赛的定位就是很多水题，然后又考虑到博弈论这个知识点本来就很冷门，于是决定放一个很板的题普及一下，顺便安利一下我同学的博客 Link。
如果您认真看了上述文章，那么这道题想必非常简单。
让我们先回顾一下博弈论的基本概念，对于当前的局势，所有通过一次操作可以变成的新的局势，我们称这几种状态为当前状态的后继，同样的，当前状态为这几种状态的先驱。
如果存在一个状态的后继满足先手必败，那么当前状态为先手必胜，否则为先手必败。这个也很好理解，如果我可以通过一个操作让对手接下来“必败”，那么我一定是“必胜”的，如果我不可以，也就是每个操作都会让对手接下来“必胜”，那么我就一定是“必败”的。
细心的读者已经发现，这个和 DP 的状态转移非常相似，如果能想到这里，那么 DP 的状态也呼之欲出了。我们不妨设 fl,rf_{l,r}fl,r 表示在 [l,r][l,r][l,r] 的区间内的状态，000 表示先手必败，111 表示先手必胜。
那么接下来我们只需要完善一个简单的区间 DP 即可，具体细节请见代码（建议先从主函数开始理解，最后看 updata 函数）。
CODE
T4 踩方格 GRID
题目大意
能否在一个 N×MN \times MN×M 的方格图上，从 (x,y)(x,y)(x,y) 点开始不重复的遍历全图。
题目分析
这显然是一道找规律的题目。
对于每一个方格图，我们可以对他进行染色，这里举一个例子：
上述的样例可以用下图表示：
可见 zc 从 (2,1)(2,1)(2,1) 出发，应遍历 kkk 个蓝色格子和 k+1k + 1k+1 个灰色格子，而图中除去出发点还有 333 个蓝格和 555 个灰格，显然不符合要求。
综上，观察可得，当且仅当 N,M,x+yN,M,x+yN,M,x+y 都为奇数时，不能满足要求。
注意，当 NNN 或 MMM 为 111 时，应当单独讨论。
CODE
T5 路径 ROAD
题目大意
给定方格图，求从左上角走到右下角所有路径所经过的格子横纵和为质数的数量。
题目分析
方案一：DFS
经典的暴力算法，简单粗暴，复杂度 O(*****−2,n−1)×(n+m))O(*****−2,n−1)×(n+m))O(*****−2,n−1)×(n+m))。
方案二：遍历
我们要求解从 (1,1)(1,1)(1,1) 到 (n,m)(n,m)(n,m) 的所有路径中，经过的"质数格子"(i+ji+ji+j 为质数)的总次数。
数学表达为：
∑所有路径∑(i,j)在路径中且i+j为质数1\sum_{所有路径} \sum_{(i,j)在路径中且i+j为质数} 1 所有路径∑ (i,j)在路径中且i+j为质数∑ 1
可转化为：
∑所有满足i+j为质数的(i,j)经过(i,j)的路径数\sum_{所有满足i+j为质数的(i,j)} 经过(i,j)的路径数 所有满足i+j为质数的(i,j)∑ 经过(i,j)的路径数
此时用 dpdpdp 预处理一遍每个点到 (1,1)(1,1)(1,1) 和 (n,m)(n,m)(n,m) 的路径数，再遍历全图，复杂度 O(n×m)O(n \times m)O(n×m) ，可得 606060 分。
对于每个点，经过此点的路径数另外一种方法如下：
对于任意格子 (i,j)(i,j)(i,j)，从 (1,1)(1,1)(1,1) 到 (i,j)(i,j)(i,j) 的路径数为：
P1(i,j)=C(i+j−2,i−1)P_{1}(i,j) = C(i+j-2, i-1) P1 (i,j)=C(i+j−2,i−1)
从 (i,j)(i,j)(i,j) 到 (n,m)(n,m)(n,m) 的路径数为：
P2(i,j)=C(n−i+m−j,n−i)P_{2}(i,j) = C(n-i+m-j, n-i) P2 (i,j)=C(n−i+m−j,n−i)
因此，经过 (i,j)(i,j)(i,j) 的总路径数为：
P(i,j)=P1(i,j)×P2(i,j)=C(i+j−2,i−1)×C(n−i+m−j,n−i)P(i,j) = P_{1}(i,j) \times P_{2}(i,j) = C(i+j-2, i-1) \times C(n-i+m-j, n-i) P(i,j)=P1 (i,j)×P2 (i,j)=C(i+j−2,i−1)×C(n−i+m−j,n−i)
此方法需要预处理一遍阶乘取模，时间复杂度 O(n×m)O(n \times m)O(n×m)。
方案三：数学
令 p=i+jp = i + jp=i+j，其中 ppp 为质数。对于固定的质数 ppp，其对答案的贡献：
∑质数p∑i=max(1,p−m)min(n,p−1)C(p−2,i−1)×C(n+m−p,n−i)\sum_{质数p} \sum_{i=max(1,p-m)}^{min(n,p-1)} C(p-2, i-1) \times C(n+m-p, n-i) 质数p∑ i=max(1,p−m)∑min(n,p−1) C(p−2,i−1)×C(n+m−p,n−i)
令 k=i−1k = i - 1k=i−1。
kkk 的范围：从 max(0,p−m−1)max(0, p-m-1)max(0,p−m−1) 到 min(n−1,p−2)min(n-1, p-2)min(n−1,p−2)。
上式变为：
∑kC(p−2,k)×C(n+m−p,n−1−k)\sum_{k} C(p-2, k) \times C(n+m-p, n-1-k) k∑ C(p−2,k)×C(n+m−p,n−1−k)
上述式子中，1≤i≤n1 \le i \le n1≤i≤n，1≤j≤m1 \le j \le m1≤j≤m。
根据范德蒙德卷积恒等式：
∑kC(a,k)×C(b,c−k)=C(a+b,c)\sum_{k} C(a, k) \times C(b, c-k) = C(a+b, c) k∑ C(a,k)×C(b,c−k)=C(a+b,c)
在我们的情况下，a=p−2a = p - 2a=p−2，b=n+m−pb = n + m - pb=n+m−p，c=n−1c = n - 1c=n−1。
式子转化为：
*****−2,n−1)C(n+m-2, n-1) *****−2,n−1)
对于每个质数p，我们有：
∑iC(p−2,i−1)×C(n+m−p,n−i)=*****−2,n−1)\sum_{i} C(p-2, i-1) \times C(n+m-p, n-i) = C(n+m-2, n-1) i∑ C(p−2,i−1)×C(n+m−p,n−i)=*****−2,n−1)
这意味着：对于每个质数 ppp，所有满足 i+j=pi + j = pi+j=p 的格子被经过的总路径数恰好等于总路径数。
因此答案等于：
∑质数pC(n+m−2,n−1)\sum_{质数p} C(n+m-2, n-1) 质数p∑ *****−2,n−1)
转化为：
质数p的个数×C(n+m−2,n−1)质数p的个数 \times C(n+m-2, n-1) 质数p的个数×C(n+m−2,n−1)
其中，2≤p≤n+m2 \le p \le n+m2≤p≤n+m。
因此可以先预处理一遍阶乘取模并计算 *****−2,n−1)C(n+m-2,n-1)*****−2,n−1)，再用欧拉筛质数计算出 [2,n+m][2,n + m][2,n+m] 间质数的个数，最后将两者相乘取模即可。
时间复杂度 O(n+m)O(n + m)O(n+m)。
说明：本题解中部分数学推导由 deepseek 辅助完成。
CODE
