祝贺@cmll02登顶，获得冰红茶500mL装一瓶！

祝贺@alan__zhao登沙东顶，获得冰红茶1L装一瓶！

A. 给你一颗枪弹！

原题 International Collegiate Programming Contest, Japan Domestic D. Audience Queue 。

考虑归并排序大概是说找到每一段的所有前缀 $\max$，把它们排序，剩下的数跟着前面的前缀 $\max$ 移动。

也就是说 $t$ 的所有前缀 $\max$ 就是这里找到的所有前缀 $\max$。那么我们先找到 $t$ 的所有前缀 $\max$，然后每个数跟着哪个数就确定了。如果一个数需要成为 $t$ 的前缀 $\max$，但是左边第一个$t$ 的前缀 $\max$ 比它大，那么在它左侧的间隔必须切一刀。如果左边第一个 $t$ 的前缀 $\max$ 比它小，它左边可以切也可以不切。只有这些刀可能切，否则会产生新的前缀 $\max$，所以切所有必须切的，如果这么切不对那就无解了，如果有解则再在可以切可以不切的位置中选若干个切即可。复杂度 $O(n)$。

B. 关山以北 桦树皮纷飞

原题 XXVI POI Stage II Cyclic shifts 。

原题的交互方式比较引荐。在打算搬的时候想了怎么实现交互，发现这是个 shaber 问题。

subtask2做法是根号步地走；或者随机直到撞，然后pr分解，每次尝试剔除一个素因数。

先用 $2\lg n+O(1)$ 次倍增出一个比较粗略的答案所在区间 $[k,2k)$。然后我们在其中二分答案 $d$，从任意位置 $a$ 出发跳两次 $\frac{d}{2}$ 分别到达 $b,c$，那么$d< n$当且仅当三个点的顺序和 $a,b,c$ 循环同构，$d> n$ 当且仅当和 $a,c,b$ 循环同构，$d=n$ 当且仅当 $a=c$。总共需要 $4\lg n+O(1)$ 次。这谁想的到啊？

我其实是不会$O(\log^2 n)$的，看了一下cmll02的做法，这里等他来补好了。

C. 浪漫派的诗人

某种意义上是 CODE FESTIVAL 2016 Grand Final H. AB=C Problem 的加强版。验题人yixiuge777。

注意到秩相同的矩阵 $C$，其价值也相同，因为秩相同的矩阵可以通过初等变换变为等价标准型，而初等变换是可逆的，所以这是一个双射。

秩为 $k$ 的矩阵的个数是 $\displaystyle\frac{\prod\limits_{i=0}^{k-1}(1-q^{n-i})(q^n-q^i)}{\prod\limits_{i=0}^{k-1}(1-q^i)}$，可以 $O(n)$ 递推。这可以通过一个简单的 dp 归纳证明，设 $i$ 个向量秩为 $j$ 的方案数是 $c(i,j)$，转移考虑选一个新的向量，那么有 $q^n-q^i$ 种方案让秩增加 $1$，有 $q^i$ 种方案让秩不变。发现转移的形式很像 $q$-二项式系数 的递推式，于是可以猜到这个形式并归纳出来。

设 $f_{n-k}$ 表示秩为 $k$ 的矩阵的价值，有 $\displaystyle f_{n-k}=\sum\limits_r\frac{c(n,k)\binom{n}{r}_q}{\binom{k}{r}_q}$，因为每个秩为 $k$ 的线性空间包含 $\binom{k}{r}_q$ 个秩为 $r$ 的子空间。已经可以法法获得 60 分。

设 $\displaystyle g_k=\frac{f_k}{\prod\limits_{i=0}^{k-1}(1-q^i)}$，观察或嗯 gf 可知 $\displaystyle g_0=\prod\limits_{i=0}^{n-1}(q^n-q^i),g_1=\frac{q^n+(q^n-q^{n-1})}{1-q}\prod\limits_{i=0}^{n-2}(q^n-q^i),g_i=\frac{(1+q-3q^i)g_{i-1}+(q+q^i)g_{i-2}}{(1-q^i)^2}$，可以 $O(n)$ 递推。

算出这些之后容易 $O(n\log t)$ 计算答案。

大家都知道 $q$ 的阶很小会除 $0$，所以这个题干脆把 $q$ 都给你了，可以自行验证每个 $q$ 的阶都很大。

zhiyangfan 10:00:58 早知道打山东省队胡策了

zhiyangfan 10:01:05 被教练拉过去打的模拟赛全是答辩数学

zhiyangfan 10:01:06 我要吐了

shanlunjiajian 10:01:10 惊讶

shanlunjiajian 10:01:17 你以为胡策不是答辩数学吗

zhiyangfan 10:02:26 绝对没我们的答辩

zhiyangfan 10:02:31 实数随机，线性代数

shanlunjiajian 10:19:20

zhiyangfan

实数随机，线性代数

再想想

shanlunjiajian 10:19:24 今天有线性代数

zhiyangfan 10:19:29 ？

shanlunjiajian 10:19:29 过两天有实数随机

zhiyangfan 10:19:32 我没看你们胡策题

zhiyangfan 10:19:39 不是，这么喜欢品鉴答辩？

zhiyangfan 10:19:49 这么喜欢品鉴答辩？这么喜欢品鉴答辩？这么喜欢品鉴答辩？

shanlunjiajian 10:19:50 魔鬼笑

shanlunjiajian 10:19:57 线性代数

shanlunjiajian 10:19:59 是我出的

shanlunjiajian 10:20:26 为了中和答辩

shanlunjiajian 10:20:33 搬了两个阳间题

zhiyangfan 10:21:14 大哭

shanlunjiajian 10:22:01 我对阳间题的评价是

shanlunjiajian 10:22:07 这谁想的到啊？

青鱼赞助了100元，设立如下奖项 :

• 每场的沙东选手第一名获得冰红茶1L装1瓶，除沙东选手第一名以外的选手第一名获得500mL装1瓶。

• 如果最后sdoi.qoj.ac有至少五场比赛(不包括测试赛)，则sdoi.qoj.ac rating沙东选手第一名获得1L装3瓶，除沙东选手第一名以外的选手前两名分别获得2，1瓶，这里只计第一次参加时rating为1800的选手。

如果一名选手的多个账号同时获奖，只按排名最高的账号计一次，奖项顺延。

如果有并列，则并列的选手全部获奖，但多次计入名额，比如第一名有三个，那么后一名就是第四名。

口味自选。

群 540823918 的消息会同步发在oj上。

有丝分裂中期，王海洋把整个地中海变为$\large\textbf{深圳中学}$的内海。有丝分裂后期，$\Huge\text{2023 沙东唱队互唱 ShanLunjiaJian Contest}$将于2023-6-12上午8:00举行!本场比赛5h 3题，IOI赛制，唱队互唱难度，相信可以在NOI之前给大家一颗枪弹。

本场比赛沙东选手第一名可以获得$\huge\text{冰红茶1L装}$一瓶，除沙东选手第一名外的第一名可以获得$\Large\text{冰红茶500mL装}$一瓶，口味自选。感谢青鱼的赞助。

加群 540823918 获得更多信息。