祝贺@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 这谁想的到啊？
