模拟赛题解/2025.9.13 模拟赛

T1-A（a）

题面

一个卖饮料的售货机，价格为 $r$ 元一瓶，内部已有 $d$ 枚 $1$ 元硬币用于找零。 现在你有 $b$ 张 $10^6$ 元纸币和 $c$ 枚 $1$ 元硬币。已知售货机每次只能买一瓶饮料，且只 会用硬币进行找零，请求出你最多能买多少瓶饮料。

$0\leq b,c,d\leq 10^9,1\leq r\leq10^9$。

题解

首先答案有上界 $\lfloor\frac{b\times 10^6+c}{r}\rfloor$。

注意到无论如何交易，纸币与硬币的总数是不变的，所以可以把每次交易看成是分配纸币与硬币给售货机。

不妨设现在购买了 $n$ 瓶饮料（不超过上界），那么售货机里会有 $nr+d$ 块钱，在最优策略下就会有 $(nr+d) \bmod 10^6$ 个硬币，此时只要 $c+d\geq (nr + d)\bmod10^6$ 就一定可以满足。

于是答案即为让上式不满足的最小的 $n$。因为其肯定有一个 $10^6$ 的循环节，所以枚举一遍即可。也可以用数学方法做到一个 $\log$。

T2-B（b）

题面

我们称一个 $n\times n$ 的矩阵是好的，当且仅当： • 该矩阵的每一行是 $1\cdots n$ 的一个排列 • $M_{i,j}\not=M_{i+1,j}(1\leq i<n,1\leq j\leq n)$ 定义矩阵转换而来的数字串 $f(M)$ 是一个长度为 $n\times n$ 的串，且 $f(M)_{(i−1)\times n+j}=M_{i,j}$ 现在给定一个好的矩阵 $M$，求有多少个好的矩阵 $M'$ 满足 $f(M')$ 的字典序小于 $f(M)$，答案对 $998244353$ 取模。

$1\leq n\leq2000$。

题解

考虑按位从小到大枚举。

假设现在枚举到 $(x,y)$，并且默认 $M'$ 前面与 $M$ 相同，只在 $(x,y)$ 位置上比 $M$ 小。设 $M'_{x,y}=k$，那么根据 $k$ 是否在 $M_{x−1,y+1\sim n}$ 中出现分类，最终都可以规约到如下的“类”错排问题：

已知 $N$ 个数，用里面的 $A$ 个数和外面的 $N−A$ 个数排列，求错排方案数。

设其方案数为 $f_{N,A}$，那么就可以用类似错排序列的递推方法求解：

1. $N=A$，此时就是错排问题；
2. $N>A$，考虑序列最后一个位置（不在 $A$ 个数里），那么分类讨论填在这个位置 上的数：

• 填了 $A$ 个数里面的数，此时有 $f_{N−1,A−1}$ 种
• 填了外面的数，此时有 $f_{N−1,A}$ 种

于是就有 $f_{N,A}=A\times f_{N−1,A−1}+(N−A)\times f_{N−1,A}(N > A)$。

最后只需要在枚举同一排的时候用树状数组动态维护当前没被用过且出现在 $M_{x−1,y+1\sim n}$ 的数的个数。

时间复杂度 $O(n^2\log n)$。

T3-C（c）

题面

现在有一根数轴，数轴上有 $n$ 个带编号的点。在时刻 $t=0$，编号为 $i$ 的点在位置 $x_i$，有初速度 $v_i\in{1,−1}$。保证初始所有点的坐标互不相同。 接下来所有点一起开始运动。如果在时刻 $t$，编号为 $x$ 的点向右运动，编号为 $y$ 的点向左运动碰撞在了一起，把这个碰撞事件记为三元组 $(t,x,y)$，并令 $vx\leftarrow−vx,vy\leftarrow−vy$ 然后继续运动。注意：在同一时刻 $t$ 可能有不止一对点发生了碰撞，但是这些碰撞事件相互独立，可以按任意顺序处理碰撞。 把所有碰撞事件的三元组 $(t,x,y)$ 按字典序从小到大排序。对于给定的 $l$ 和 $r$，找到第 $l$ 个到第 $r$ 个事件并按顺序输出这些事件的 $x$ 和 $y$。保证至少有 $r$ 次碰撞存在。

$1\leq n\leq3\times10^5$，$−10^9\leq x_i\leq10^9$，$v_i\in{1,−1}$，$1\leq l\leq r\leq10^{10}$，$r−l\leq 10^5$。

题解

如果不考虑每个点的编号，一次碰撞可以看作是两个点互相穿过了彼此而不改变方向。所以对于任意时间 $t$，我们可以知道每个点的坐标。

如果考虑每个点的编号，发现每次碰撞并不会改变带编号的点的相对顺序。

有了上述两个观察，我们可以先进行二分，对于给定的时间 $t$ 计算出截止到时刻 $t$ 一共经历了多少次碰撞，从而得到第 $l$ 次碰撞的时间 $t_l$。同理得到 $t_r$。

接下来，我们先计算出在时刻 $t_l$ 所有点的坐标。我们知道编号的相对顺序不变，那么就可以按顺序对应出当前每个点的编号。接下来找到所有在时刻 $[t_l,t_r]$ 的碰撞。同一个时刻可能存在多个碰撞，但这些碰撞的点互不相同，所以至多存在 $O(n)$ 个同一时刻的碰撞。时刻 $[t_l+1,t_r−1]$ 的碰撞次数 $\leq r−l\leq 10^5$，所以时刻 $[t_l,t_r]$ 的所有碰撞总数也是 $O(n)$ 的。

最后，按顺序模拟这些碰撞，找到对应的三元组并将三元组按给定规则排序，输出对应的区间即可。

时间复杂度为 $O(n\log(n+V))$，这里 $V$ 是值域，瓶颈在二分。二分之后的计算可以先排好序然后用双指针加速。复杂度是两个 $\log$ 的小常数程序也有可能通过本题。

T4-D（d）

题面

有一个积性函数 $^{[1]}f$ 满足如下条件（其中 $p$ 为质数）： • $f(1)=1$ • $f(p)=p^{114514}$ • $f(pc)=p^{229028}(p+1)^{1919810(c−2)}(c\geq 2)$ 现在有一个长为 $n$ 的序列 $a$，并对其进行 $q$ 次操作，操作分为如下两种：

1. 把 $a_x$ 改成 $y$
2. 查询 $\displaystyle f(\prod_{i=x}^y a_i)\bmod 1019260817$

请你回答所有查询操作的答案。你可能需要在线回答这些询问。 $[1]$：积性函数 $f$ 拥有如下性质：若 $a$ 与 $b$ 互质，则 $f(a\times b)=f(a)\times f(b)$。

$n,q\leq 10^5,1\leq a_i\leq10^6$。

题解

考虑 $f(p^c)=p^{114514c}\times(\frac{(p+1)^1919810}{p^114514})^max(c−2,0)$。

然后两部分是独立的，我们可以先求出第一个的乘积，再乘上第二个的乘积。

第一个的乘积其实就是 $\displaystyle(\prod_{i=x}^y a_i)^{114514}$，线段树维护即可。

第二部分可以考虑将每个数拆成 $\leq1000$ 的质因子和至多一个 $>1000$ 的质因子。

对于 $\leq1000$ 的质因子直接枚举每个质因子，用 $O(\sqrt n)$ 修改 $O(1)$ 查询的分块维护区间该质因子的个数。

对于 $>1000$ 的质因子，考虑把所有 $=p$ 的质因子拿出来，设其位置为 $a_1,a_2,\cdots,a_m$，然后加入若干条线段 $(a_1,a_3),(a_2,a_4),\cdots,(a_m−2, a_m)$，每条线段的权值为 $\frac{(p+1)^{1919810}}{p^{114514}}$，那么只需要求 $[l,r]$ 内部所有线段的权值乘积就行了。用树套树做到两个 $\log$，修改用 $\text{set}$ 动态维护线段。

时间复杂度大概 是 $O(n\sqrt{n}\log n)$ 级别的？反正跑不满。