2024.10.17 题目

题解：2024.10.17 模拟赛

语言

找规律 前缀和

有一种新的语言，这种语言有 $26$ 个单次分别对应 $\text{a}$ 到 $\text{z}$。其中，第 $i$ 个字符词性为第 $a_i$ 类。第 $1\sim 7$ 类分别为：A, N, A/N, V, A/V, N/V, A/N/V。一个合法的句子为名词词组+动词+名词词组。名词词组可以由一个名词（N）、一个形容词（V）加一个名词词组、两个名词词组组成。现在给定字符序列 $S$，判断 $S$ 能否组成一个合法的句子。

色球

链表 模拟 平衡树

有 $n$ 种颜色的小球，每种颜色有无限个。还有 $n$ 个球桶，每个球桶能够容下无限多的小球。一开始的球桶都是空的，有 $m$ 次操作，每次操作都是以下三种的任意一种：

• 把 $x$ 个颜色为 $y$ 的彩色小球放到第 $z$ 个桶的最上面；
• 把嘴上面的 $x$ 个小球从第 $z$ 个桶里面拿出来，并输出最后拿出来的球的颜色。保证第 $z$ 个桶里面的球数不小于 $x$ 个；
• 把第 $u$ 个桶里面的小球依次从顶部拿出并放入第 $v$ 个桶内。

斐波

线段树 数学

令 $fib(n)=\{\begin{array}{ll}0& \text{if }n=0\\ 1& \text{if }n=1\\ fib(n-1)+fib(n-2)& \text{else}\end{array}$。假设 $S$ 为可重集 $\{s_1,s_2,\cdots ,s_{|s|}\}$，则 $f(S)$ 定义为 $f(S)=\sum _{T\subseteq S}{\left[fib(\sum _{s\in T}s)\right]}^2$。有一个数组 $a_1,a_2,\cdots ,a_n$，会进行 $q$ 次操作。每次操作都是以下两种操作的一种：

• 把 $a_p$ 变为 $v$；
• 计算 $\sum _{i=l}^r\sum _{j=i}^{r}f(\{a_i,a_{i+1},a_j\})$。司马玩懿

对于操作 $2$，答案对 $998244353$ 取模。

偶数

数学 快速幂

对于一个正整数（去掉前导 $0$），如果它在十进制下位数为偶数且前一半与后一半一致，则称这个数为“偶数”。对于一个“偶数”，牛牛可以在这个数后面继续添加数字，使它成为一个新的偶数。牛牛总是添加最少的数字获得新的“偶数”，因此添加的方式唯一。

牛牛会对于一个偶数 $u$，一直产生新的偶数，直到偶数的位数超过给定的正整数 $n$。牛牛会多次询问你这个偶数的第 $l$ 到 $r$ 为所组成的整数摸 $998244353$ 的值是多少。$T$ 组数据。