1227 第 1 场 算法季度赛

• 比赛链接：https://www.lanqiao.cn/oj-contest/season-1/
• 题解回放：https://www.bilibili.com/video/BV1RT4y1s7dt/

T1. 新年快乐【算法赛】

问题描述

亲爱的选手们，

$2023$ 即将结束，在这一刻，我想问你们：是否还记得那些深夜解题的时光？当寂静的夜晚只有键盘的敲击声和心中的思绪争鸣时，你们一次又一次地翻开别人的代码，寻找解决难题的答案。那份坚持，那份执着，已经成为了你们不可或缺的一部分。

是否还记得每一场比赛的紧张时刻？当比赛的钟声响起，你们如同战士一般坐在电脑前，用智慧和勇气与时间赛跑。每一个 AC（Accept）的提示音都是对你们努力的肯定，每一个 WA（Wrong Answer）都激励你们不断前进。

而那些 AK 的瞬间，那份喜悦和成就感是多么难以忘怀！它们不仅是分数的累积，更是你们无数个日夜努力的见证。每一个成功的提交都是你们智慧的火花，在竞赛的历程中熠熠生辉。

现在，站在新的起跑线上，可能会有疲倦，可能会有疑惑，但请不要忘记那些夜晚的坚持和比赛的激情。让它们成为你们前进的动力，让这一路上的艰辛和荣耀共同铸造你们的未来。

愿你们在即将到来的 $2024$ 年再次感受到 AK 的喜悦，愿那份喜悦伴随着你们每一次的尝试和努力。不论前路如何，你们都已经是赢家。

所以，请为自己加油吧，输出 2024 AK 即可通过本题。

输入格式

本题无输入。

输出格式

根据题意输出一行表示答案。

T2. 蓝桥圣诞树【算法赛】

问题描述

圣诞节到了，蓝桥学院门口摆放了一棵具有 $N$ 个节点的二叉圣诞树，每个节点要么为红色要么为绿色。

同学们正在讨论这颗圣诞树的染色是否足够美观，具体地说，如果存在三个连续的节点颜色相同，那么该圣诞树被认定为不美观的圣诞树。

现在给定一颗圣诞树请你判断它是否美观，如果美观则输出 YES，否则输出 NO。

输入格式

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

对于每组测试数据：

• 第一行输入一个整数 $N$ 表示二叉圣诞树的节点个数。
• 第二行输入一个长度为 $N$ 的字符串 $S$，$S_i$ 表示第 $i$ 个节点的颜色，$0$ 为绿色，$1$ 为红色。
• 接下来 $n-1$ 行每行输入两个整数 $u,v$ 表示 $u,v$ 之间存在一条边。

输出格式

对于每个测试用例输出一个字符串表示答案。

样例输入

1
3
101
1 2
2 3

样例输出

YES

评测数据范围

$1 \leq t \leq 1000$，$3 \leq N \le 30$，$0 \leq S_i \leq 1$，$1 \leq u,v \leq N$，$u \ne v$。

保证给定的是一颗二叉树。

T3. 空间复杂度【算法赛】

问题描述

在计算机科学中，空间复杂度是指算法在运行过程中所临时占用存储空间大小的量度。空间复杂度与时间复杂度一样，是衡量算法效率的重要指标之一。

在编程中，特别是在内存限制严格的环境下，我们需要考虑空间复杂度来优化程序。因此，掌握空间复杂度的概念和计算方法对于编写高效程序至关重要。

现在，给定一系列程序的内存限制，这些内存限制均由一个整数 $X$ 和一个单位 $S$ 构成。例如，$X=256$，单位 $S=\text{MB}$，则内存限制为 $256\text{MB}$。而你要做的是，在每个给定的内存限制下，计算出最多可以声明一个多大的 P 类型数组。已知，一个 P 类型的变量占用的内存大小为 $Y$ 个字节。

在本题中，我们假设程序本身不占用任何额外空间。

但在实际编程中，除了数组本身的空间，还需要考虑其他可能的变量和数据结构占用的空间。因此，我们需要仔细分析算法的空间复杂度，并采取相应的优化策略，以确保程序在内存限制下的正确运行。

输入格式

第一行包含一个整数 $T$（$1\leq T \leq 10^3$），表示有 $T$ 组测试数据。

接下来的 $T$ 行中，每行包含一个整数 $X$（$1 \leq X \leq 10^6$），一个字符串 $S$（$S \in \lbrace \text{MB}, \text{KB}, \text{B}\rbrace$） 和一个整数 $Y$（$1\leq Y \leq 10$），表示的内存限制以及一个类型 P 的变量占用的字节大小。

输出格式

对于每组测试数据，输出一行一个整数，表示在给定的内存限制下，可声明的 P 类型数组的最大长度。

样例输入

3
10 B 4
1 KB 5
2 MB 6

样例输出

2
204
349525

T4. 开关【算法赛】

问题描述

在圣诞节的晚上，一个名叫爱丽丝的小女孩邀请她的朋友们来家里玩一个特别的游戏：开关灯小游戏。

他们将 $N \times N$ 的圣诞节彩灯摆放成 $N \times N$ 的网格状，初始时所有灯泡均为关闭状态，现执行以下操作：

$\forall 1 \leq i \leq N$ 依次分别执行以下两项操作：

1. 有 $\frac{a_i}{b_i}$ 的概率触发事件：翻转第 $i$ 行所有灯泡的开关状态（即将关闭的灯泡变成打开，将打开的灯泡变成关闭）。
2. 有 $\frac{c_i}{d_i}$ 的概率触发事件：翻转第 $i$ 列所有灯泡的开关状态（即将关闭的灯泡变成打开，将打开的灯泡变成关闭）。

爱丽丝想知道最终期望有多少个灯泡是亮的，答案对 $998244353$ 取模。

令 $M=998244353$ ，可以证明所求概率可以写成既约分数 $\dfrac{p}{q}$ 的形式，其中 $p,q$ 均为整数且 $q\ ot\equiv 0 (mod \ M)$。输出的整数应当是 $p·q^{-1}(mod\ M)$ 即 $p·q^{M-2}(mod\ M)$。

输入格式

第一行包含 $1$ 个正整数 $N$。

第二行包含 $N$ 个整数，第 $i$ 个数表示 $a_i$。

第三行包含 $N$ 个整数，第 $i$ 个数表示 $b_i$。

第四行包含 $N$ 个整数，第 $i$ 个数表示 $c_i$。

第五行包含 $N$ 个整数，第 $i$ 个数表示 $d_i$。

输出格式

输出共 $1$ 行，包含 $1$ 个整数，表示最终答案，答案对 $998244353$ 取模。

假设最终答案为 $\frac{x}{y}$ 满足 $(x,y)=1$，你只需要输出 $x \times y^{998244351}$。

样例输入

2
1 1
1 1
1 1
2 2

样例输出

2

评测数据规模

对于所有测评数据，$1 \leq N \leq 10^5$，$1 \leq a_i \leq b_i < 998244353,1 \leq c_i \leq d_i<998244353$。

T5. 异或与求和【算法赛】

问题描述

在圣诞节的早晨，小男孩艾登醒来，他发现了一件神奇的事情：他的圣诞袜里装满了糖果和礼物。艾登非常开心，他决定去找他的好朋友露西分享这份喜悦。

露西的家离艾登的家不远，两人经常一起玩耍。当艾登来到露西家时，他发现露西正一脸困惑地坐在圣诞袜前。露西的圣诞袜里也装满了礼物，但与艾登不同的是，露西的袜子里还夹着一个神秘的小纸条。

纸条上写着：“这是一个位运算的挑战，只有解决了这个问题，你才能获得圣诞节的大礼。”艾登和露西无法解决这个问题，所以他们来向你进行求助。

现在给定长度为 $N$ 的序列 $\\{a\\}$，一组四元组 $(i_1,i_2,i_3,i_4)$ 满足 $1 \leq i_1<i_2<i_3<i_4 \leq N$ ，其权值定义为 $(a_{i_1} \oplus a_{i_2}) + (a_{i_3} \oplus a_{i_4})$，其中 $\oplus$ 表示异或操作。现在请你求解所有合法四元组的权值之和，即求解

$$\sum_{1 \leq i_1 < i_2 < i_3<i_4 \leq N}(a_{i_1} \oplus a_{i_2}) + (a_{i_3} \oplus a_{i_4})$$

由于答案可能很大，你只需要输出答案对 $998244353$ 取模后的结果。

输入格式

第一行包含 $1$ 个正整数 $N$。

第二行有 $N$ 个正整数，第 $i$ 个表示权值 $a_i$。

输出格式

输出共 $1$ 行，包含 $1$ 个整数，表示最终答案，答案对 $998244353$ 取模。

样例输入

8
1 2 3 4 5 6 7 8

样例输出

828

评测数据规模

对于所有测评数据，$1 \leq N \leq 10^5,1 \leq a_i \leq 10^9$。

T6. 数字求和【算法赛】

问题描述

圣诞节来了，但是可怜的杰克还没有完成他的数学作业，可怜的杰克必须完成他的数学作业之后才能和他的小伙伴们一起享受圣诞假日，其中一道题的题目是这样的：

定义 $f(x)$ 为 $x$ 的每一位数码之和，例如 $f(114)=1+1+4=6$，询问有多少个 $N$ 位正整数 $x$，满足 $f(x)=M$，答案对 $998244353$ 取模。

请你帮助他解决这个问题。

注意 $N$ 位正整数不能存在前导零。

输入格式

第一行包含 $2$ 个正整数 $N,M$。

输出格式

输出共 $1$ 行，包含 $1$ 个整数，表示最终答案，答案对 $998244353$ 取模。

样例输入

3 3

样例输出

6

样例解释

满足的解有 $300,201,210,120,102,111$。

评测数据规模

对于所有测评数据，$1 \leq N,M \leq 10^6$。

T7. 集合统计【算法赛】

问题描述

在遥远的北国小镇，住着一位名叫艾丽丝的小女孩。艾丽丝对数学有着浓厚的兴趣，特别是集合论。在她的眼中，世界就像一个巨大的集合，而圣诞节则是一个集合与集合之间奇妙的交集。

圣诞节前夕，艾丽丝兴奋地装饰着圣诞树，她用各种颜色的彩灯、闪亮的装饰品和精心挑选的礼物将树装饰得五彩斑斓。她将每个礼物看作是一个集合，每个集合都有独特的元素。有的集合是玩具，有的集合是书籍，还有的集合是美食，现在艾丽丝希望你帮助求解以下集合论问题。

给定正整数 $l,r,k$，请你求解有多少个不可重非空正整数集合 $A$，满足：

1. 集合中所有的数均为 $[l,r]$ 中的正整数。
2. 若存在正整数 $x \in A$，那么一定有 $kx \notin A$。

由于答案可能很大，你只需要输出答案对 $998244353$ 取模后的结果。

输入格式

第一行包含一个正整数 $T$，表示数据组数。

之后对于每组数据，输入共一行，包含 $3$ 个正整数 $l,r,k$。

输出格式

对于每组数据输出一行，输出 $1$ 个整数，表示最终答案，答案对 $998244353$ 取模。

样例输入

2
1 3 2
114514 1919810 233

样例输出

5
183010726

评测数据规模

对于所有测评数据，$1 \leq k \leq 10^{18},1 \leq l \leq r \leq 10^{18},1 \leq T \leq 10^4$。