1223 第 2 场 小白入门赛/强者挑战赛

• 小白入门赛：https://www.lanqiao.cn/oj-contest/newbie-2/
• 强者挑战赛：https://www.lanqiao.cn/oj-contest/senior-2/
• 题解回放：https://www.bilibili.com/video/BV1kC4y1q75p/

T1. 蓝桥小课堂-平方和【算法赛】

问题描述

蓝桥小课堂开课啦！

平方和公式是一种用于计算连续整数的平方和的数学公式。它可以帮助我们快速求解从 $1$ 到 $n$ 的整数的平方和，其中 $n$ 是一个正整数。

平方和公式的表达式如下：

$$1^2 + 2^2 + 3^2 + \ldots + n^2 = \frac{{n \cdot (n + 1) \cdot (2n + 1)}}{6}$$

这个公式可以简化计算过程，避免逐个计算整数的平方并相加。通过直接使用平方和公式，我们可以更高效地求解大规模的平方和问题。

举个例子，如果要计算从 $1$ 到 $10$ 的整数的平方和，可以将 $n$ 的值设为 $10$ ，然后将其代入公式中计算：

$$1^2 + 2^2 + 3^2 + \ldots + 10^2 = \frac{{10 \times (10 + 1) \times (2 \times 10 + 1)}}{6}$$

现在，学习完平方和公式的你需要接受小蓝的考验了。小蓝会给定一个整数 $n$，请你求出 $\sum_{i=1}^{n} i^2$ 的值。

输入格式

输入一行包括一个整数 $n$。

输出格式

输出一个整数表示答案。

样例输入

10

样例输出

385

评测数据范围

$1 \leq n \leq 10^6$。

T2. 质数王国【算法赛】

问题描述

在数字王国发生战乱后，小蓝带领着 $N$ 个数字逃往了隔壁的质数王国。然而，质数王国只允许质数进入。小蓝作为领袖，可以执行以下操作之一：

• 选择一个数字 $x$ 并将其增加 $1$。
• 选择一个数字 $x$ 并将其减少 $1$。

现在，请你帮小蓝计算使得 $N$ 个数字都能进入质数王国的最少操作次数。

输入格式

第一行包括一个整数 $N$ 。

第二行输入 $N$ 个整数 $A_1,A_2,A_3,\cdots,A_n$ 表示出逃的数字。

输出格式

输出一个整数表示答案。

样例输入

5
1 2 3 4 5

样例输出

2

说明

将 $A_1,A_4$ 加 $1$ 后数组变为 $\lbrace 2,2,3,5,5 \rbrace$，所有的数字都变为质数，所以最小的操作数为 $2$。

评测数据范围

$1 \leq N \leq 10^5$。

$0 \leq A_i \leq 10^5$。

T3. 房顶漏水啦【算法赛】

问题描述

小蓝家的房顶是一个边长为 $n$ 的正方形，可以看成是由 $n \times n$ 个边长为 $1$ 的小正方形格子组成。

从上到下第 $i$ 行、从左到右第 $j$ 列的格子用 $(i,j)$ 表示。

小蓝的家由于年久失修，导致房顶有一些地方漏水。总共有 $m$ 处漏水的地方，我们用 $(x_1, y_1),(x_2,y_2)...(x_m,y_m)$ 来表示。

于是小蓝来到了五金店，五金店贩卖着一些正方形木板，木板的种类有 $n$ 种，第 $i$ 种木板的边长为 $i$。小蓝需要一块能够覆盖所有漏洞的木板，请问小蓝需要购买木板的最小边长是多少？

输入格式

第一行输入两个整数 $n,m$。

接下面 $m$ 行，每行两个整数 $(x_i, y_i)$ 代表第 $i$ 个漏洞的位置。

输出格式

输出一个整数，代表木板的最小边长。

样例输入

5 3
3 3
5 3
4 4

样例输出

3

说明

房顶漏洞如下图所示，使用 $3 \times 3$ 的正方形可以覆盖掉所有的漏洞。

样例

评测数据范围

$2 \le n \le 10^{10}, 1 \le m \le \min(n^2, 10^4), 1 \le x_i,y_i \le n$。

保证所有的 $(x_i, y_i)$ 互不相同。

T4. 取余【算法赛】

问题描述

在学了数论课之后，小桥给了小蓝一个挑战：

小桥规定了两个整数变量 $a,b$，$a$ 的取值范围在 $[1, A]$，$b$ 的取值范围在 $[1, B]$，他们相互组合会形成 $A \times B$ 个数对 $(a, b)$，我们定义：

$$f(a, b) = a - b \times \lfloor \frac{a}{b} \rfloor$$

也就是，$f(a,b)$ 等于 $a$ 对 $b$ 取模的结果。

小桥问小蓝，在所有的数对中，$S \le f(a, b) \le T$ 的有多少个。

小蓝不会，于是来问你，你需要回答这个问题。

输入格式

第一行输入四个整数：$A,B,S,T$。

输出格式

输出一个整数，表示合法的数对的数量。

样例输入

3 3 1 2

样例输出

4

说明

以下数对是合法的：

$(1,2),(3,2),(1,3),(2,3)$。

评测数据范围

$1 \le A, B \le 10^7, 0 \le S \le T \le 10^7$。

T5. 数学尖子生【算法赛】

问题描述

小蓝和小桥是蓝桥班上的数学尖子生，他们之间总是充满了各种竞争。

有一天他们进行了一场数学游戏，小蓝每次会给定两个正整数 $a$ 和 $n$，小桥需要回答区间 $[1,n]$ 有多少个数 $b$ 满足 $f(b)=a$。

• 定义函数 $f(x)$ 表示非 $x$ 因数的最小正整数，比如 $f(6)=4$，因为 $1,2,3$ 均为 $6$ 的因数，而 $4$ 不是 $6$ 的因数。

作为小桥最好的朋友，请你帮她一起解决这个问题。

输入格式

第一行输入一个整数 $t$ 表示测试用例数量。

接下来 $t$ 行，每行包含两个整数 $a,n$ 表示一组询问。

输出格式

对于每组询问输出一行一个数字，表示答案。

样例输入

3
2 10
3 10
16 10000000000000000

样例输出

5
4
13875013875

说明

在第一个测试用例中，$[1,10]$ 中当 $b \in(1,3,5,7,9)$ 时满足 $f(b)=2$，所以答案为 $5$。

评测数据范围

$1 \leq t \leq 10^5$，$1 \leq a \leq 10^6$，$1 \leq n \leq 10^{16}$。

T6. 扫雷【算法赛】

问题描述

扫雷是一款经典的游戏。如下图：

图片描述

规则如下。

1. 地图为 $n \times m$ 的矩阵。
2. 地图中包含地雷和数字。
3. 如果某个点是地雷块，那么用 X 表示。
4. 如果某个点是数字块，那么用 $0 \sim 8$ 表示，具体的数值为该点周围地雷的数量（最少为 $0$ 个，最多为 $8$ 个）。
5. 如果某个点未知，即可能是地雷或者数字，我们用 * 表示。

周围：对于 $(x,y)$ 点来说，周围为 $(x-1, y),(x+1, y),(x, y-1),(x, y+1),(x-1, y-1),(x-1, y+1),(x+1, y-1),(x+1, y+1)$ 八个位置。需要注意的是，超过边界的点不能算作周围的点。

了解上述规则后，我们得知，可以通过数字块推理出地雷的位置。

小蓝是扫雷高手，他点开了一局游戏。

玩了一段时间之后，他发现没法推断出来到底哪些块是地雷（如上述图片），他感到十分厌烦，觉得这个游戏有 BUG。

于是小蓝找到了你，想让你用计算机判断一下，某些地图残局是否有 BUG。

具体来说，小蓝给你一幅 $n \times m$ 的地图，地图中只包含数字和 *（不包含 X，因为不能点开雷区），小蓝想知道，对于该局面，能否直接推断出所有的 * 的值。如果可以，代表该局面的解唯一，即没有 BUG；如果不能，小蓝就是会认为该局面的解不唯一，游戏产生了 BUG。

输入格式

第一行一个整数 $T$，代表扫雷地图数量。

对于每一个地图，由以下部分构成：

1. 第一行输入两个整数 $n,m$。
2. 接下面 $n$ 行，每行输入 $m$ 个字符。

输出格式

输出 $T$ 行。

第 $i$ 行对应第 $i$ 个地图的解情况，每行输出一个字符串：输出 Single 代表只有一种解，即无 BUG，输出 Multiple 代表存在多个解，即有 BUG。

样例输入

2
3 5
01*10
011*0
00000
3 3
***
232
***

样例输出

Single
Multiple

说明

第一个样例就只有一种解：

01X10
01110
00000

第二组样例存在如下多组解：

XX1   01X   XXX
232   232   232
01X   XX1   000

评测数据范围

$1 \le n \times m \le 100, 1 \le T \le 100$。

保证输入中只包含：* 和数字字符，并且至少存在一种合法地图解，即不会存在自相矛盾的残局。

每组的 * 不会超过 $16$ 个。

T7. 魔术师【算法赛】

问题描述

小蓝是一个魔术师，他正在蓝桥大剧院表演。

台上有一排 $n$ 个盒子，编号 $1 \sim n$。表演开始之前，助手会在每个盒子里放入一个小球，小球的颜色有三种，分别为红、黄、蓝。

小蓝有 $3$ 种魔术操作：

1. 颜色互换，小蓝会选择一个区间 $[l,r]$ 和两种颜色 $a,b$，对于每一个盒子来说，如果它的编号在 $[l,r]$ 内，并且盒子内的球颜色为 $a$，那么盒子里球颜色变为 $b$，如果盒子里的球颜色为 $b$，那么盒子里球颜色变为 $a$。
2. 染色，小蓝会选择一个区间 $[l,r]$ 和两种颜色 $a,b$，对于每一个盒子来说，如果它的编号在 $[l,r]$ 内，并且盒子内的球颜色为 $a$，那么盒子里球颜色变为 $b$。
3. 分裂，小蓝会选择一个区间 $[l,r]$ 和一种颜色 $a$，对于每一个盒子来说，如果它的编号在 $[l,r]$ 内，并且盒子内的球颜色为 $a$，那么盒子里所有的球由一个分裂成两个。

补充说明：对于三种魔术，在区间内，如果不存在颜色 $a$ 的球，那么对于颜色 $a$ 的操作将不会发生；如果不存在颜色 $b$ 的球，那么同理；如果都不存在，那么什么都不会发生。

例如：对于颜色互换术而言，如果不存在颜色为 $a$ 的球，但是存在颜色为 $b$ 的球，那么颜色为 $b$ 的球将被变成 $a$，但是将没有颜色为 $a$ 的球变成 $b$。

小蓝会不断的重复上述三种操作。

你是小蓝的助手，每一次操作后，你都需要回答小蓝，每种颜色的球现在有多少个。答案可能很大，请对 $998244353$ 取模。

输入格式

第一行输入两个整数 $n,m$。

接下来一行，输入 $n$ 个整数 $c_1, c_2, c_3,...,c_n$，每个盒子里球的初始颜色，为了方便，我们用数字 $1,2,3$ 来表示颜色红、黄。蓝，下述操作同理。

接下来 $m$ 行，每行包含一个操作，先输入三个整数 $l,r,opt$， $l,r$ 代表操作区间为编号在 $[l,r]$ 中的盒子，$opt$ 代表操作种类，后续输入如下：

1. 如果 $opt = 1$，输入两个整数 $a,b$，代表进行颜色互换术，将区间内 $a,b$ 颜色互换，即颜色为 $a$ 的球变为颜色 $b$，颜色为 $b$ 的球变为颜色 $a$。
2. 如果 $opt = 2$，输入两个整数 $a,b$，代表进行染色术，将区间内 $a$ 颜色球变为颜色 $b$。
3. 如果 $opt = 3$，输入一个整数 $a$，代表进行分裂术，将区间内所有 $a$ 颜色的球由一个分裂成两个。

输出格式

输出 $m$ 行，每行三个整数，表示这次操作结束后，所有盒子中颜色分别为 $1,2,3$ 的球的数量，答案可能很大，请对 $998244353$ 取模。

样例输入

5 3
1 1 2 3 1
1 3 1 1 2
2 3 2 1 2
2 4 3 2

样例输出

2 2 1
1 3 1
1 5 1

说明

第一次操作后：$\lbrace 2_1,2_1,1_1,3_1,1_1 \rbrace$。值代表该盒子里球的颜色，角标代表该盒子的球数量。

第二次操作后：$\lbrace 2_1,2_1,2_1,3_1,1_1 \rbrace$。

第三次操作后：$\lbrace 2_1,2_2,2_2,3_1,1_1 \rbrace$。

输入输出数据量较大，请使用较快的输入输出方式。

评测数据范围

$1 \le n, m \le 10^5, 1 \le opt, c_i, a, b\le 3, 1\le l \le r \le n$。

保证 $a \neq b$。

T8. 扫雷 II【算法赛】

问题描述

扫雷是一款经典的游戏。如下图：

图片描述

规则如下。

1. 地图为 $n \times m$ 的矩阵。
2. 地图中包含地雷和数字。
3. 如果某个点是地雷块，那么用 X 表示。
4. 如果某个点是数字块，那么用 $0 \sim 8$ 表示，具体的数值为该点周围地雷的数量（最少为 $0$ 个，最多为 $8$ 个）。
5. 如果某个点未知，即可能是地雷或者数字，我们用 * 表示。

周围：对于 $(x,y)$ 点来说，周围为 $(x-1, y),(x+1, y),(x, y-1),(x, y+1),(x-1, y-1),(x-1, y+1),(x+1, y-1),(x+1, y+1)$ 八个位置。需要注意的是，超过边界的点不能算作周围的点。

小蓝是扫雷高手，于是他在原来扫雷游戏的基础上改动了一下。

现在给定你一个 $3 \times m$ 的地图，其中第二行全部都不是地雷，第一行和第三行都是未知，小蓝将第二行的数字全部告诉你，请问这幅地图有多少种不同的可能？

也就是说，假设每个格子有 $10$ 种情况（X 或者 $0 \sim 8$），那么 $3 \times m$ 的地图总共有 $10^{3m}$ 情况，请你找出满足以下两个要求的地图数量：

1. 地图合法，即满足扫雷规则。
2. 第二行与给定第二行的值相同。

答案可能很大，请对 $998244353$ 取模。

输入格式

第一行输入一个整数 $m$。

第二行输入 $m$ 个整数 $p_1, p_2, p_3, ..., p_m$，代表第地图中 $2$ 行第 $i$ 列的值。

输出格式

输出一个整数，代表可能的种类数，答案可能很大，请对 $998244353$ 取模。

样例输入

3
2 3 2

样例输出

8

说明

以下 $8$ 种。

XX1  01X  XXX  000  X2X  1X1  1XX  X10
232  232  232  232  232  232  232  232
01X  XX1  000  XXX  1X1  X2X  X10  1XX

评测数据范围

$1 \le n \le 5 \times 10^5, 0 \le p_i \le 8$。

T9. 香煎七十二餐馆【算法赛】

问题描述

小蓝开了一家餐馆：“香煎七十二餐馆！”

据说共有七十二道菜，每道菜煎炸的次数不一，最简单的只需要煎一次，最复杂的需要煎炸整整七十二次！

开店第一天，举办了一场餐馆派对，免费接待 $n$ 位顾客。

$n$ 位顾客坐在一个长桌上，编号 $1 \sim n$。小蓝的餐馆共有 $72$ 道菜，编号 $1 \sim 72$。每位顾客只会点一道菜，$n$ 位顾客中有 $m$ 位顾客已经点好了菜，剩下的顾客由小蓝推荐点菜。

由于每位顾客用餐的时候，都会对菜品评头论足，如果两个相邻的顾客吃的是同一道菜，他们难免会讨论，有一些吹毛求疵的顾客可能借此将消极情绪传播给他人。为了避免上述情况发生，导致影响口碑，小蓝将安排相邻的顾客的菜肴都不相同。

请问有多少种不同的安排方案，答案可能很大，请对 $998244353$ 取模。

相邻：即编号相邻，$i$ 与 $i-1$ 和 $i+1$ 相邻。注意，这是一张长桌，所以 $1$ 和 $n$ 并不相邻。

输入格式

第一行输入两个整数 $n,m$。

接下来 $m$ 行，每行两个整数 $p_i, c_i$，表示编号为 $p_i$ 的人已经点好了一份编号为 $c_i$ 的菜肴。

输出格式

输出一个整数，表示合法的安排方案数。答案可能很大，请对 $998244353$ 取模。

样例输入

3 1
2 1

样例输出

5041

说明

第一个顾客可以安排编号 $2 \sim 72$ 的菜肴，第三位顾客可以安排编号 $2 \sim 72$ 的菜肴。共计 $71^2=5041$。

评测数据范围

$0 \le m\le 10^5, 3 \le n \le 10^{15}, 1 \le c_i \le 72, 1 \le p_i \le n$。

保证所有的 $p_i$ 不相同。