比赛真的变简单了好多呢。
Backpack
题面
考场
首先想了一个贪心。（部分背包类似，把所有物品按照一个性价比排序。）
然后黑了自己。
然后开始 $dp$ ，发现是一个 $O(nm).$ ：
$\Large dp_j=\max\{dp_{j-w_i}+v_i\}.$
搞完后面的之后回头来看，发现 $a,b$ 的范围只有 $[1,100]$，那可以考虑做一个桶，把 $a$ 一样的物品只存它们的 $\max v.$
然后就得到了一个 $O(m\max a)$ 的算法，能拿 $60pt.$ 稍微考虑了一下矩乘但是好像不太好写就没管了。
出分： $60pt.$
正解
贪心。？？
没错，一开始的类似部分背包的贪心有一定的正确性。可以大概的猜到，最优解里面一定会有很大一部分用性价比最大的物品组成的。所以我们考虑剩下多少贪心不一定正确。
首先在任意的 $n$ 个数中，一定有某些数之和是 $n$ 的倍数。证明方法考虑它们的 $n+1$ 个前缀和，由抽屉原理，一定有两个在模 $n$ 意义下同余。所以他们之差所对应的区间的数之和一定是 $n$ 的倍数。
如此一来，只要留下 $a_s$ 个数即可，不然可以通过用 $s$ 替换里面的若干个和是 $a_s$ 的倍数的物品，这样肯定会更优。（ $s$ 即为性价比最高的物品。）
这样把剩下的很少的物品做一个 $dp$ 即可。
$code:$
矩乘！
看这个 $m$ 的范围应该可以大概想到矩乘优化一下 $DP.$ 那么就是考虑怎么做转移矩阵了。
那么我们考虑现在的答案会从前面的哪里转移过来，用多少代价。我们发现，我们在 $i$ 的时候，会从所有的 $i-w_j$ 转移过来，并且答案是 $\max\{f_i+v_j\}.$ 所以就可以考虑构建一个 $100\times100$ 的矩阵，每次乘法是做的加法取 $\max.$ 那么矩阵具体应该是什么样的呢？
那么我们考虑从 $\large f_{i-k+1}\to f_i$ 转移到 $\large f_{i-k + 2}\to f_{i+1}.$ （其中 $k=\max\{w_i,~v_i\}$）首先，之前的后 $k-1$ 项和之后的前 $k-1$ 项是要相同的，考虑到是加法取 $\max$ ，可以只算矩阵中非 $-1$ 的数，并把对应斜对角线赋为 $0.$ 这样可以保证前 $k-1$ 项了。那么最后一行的矩阵就是直接和转移方程挂钩了。那么就是在所有的 $w_i$ 的位置上赋 $v_i$ 的值即可。其他空位赋 $-1.$
完整矩阵如下图：（最后一行假定被所有物品填满了，且 $w_i=i.$）
$\large\left[\begin{matrix} -1 & 0&-1&\cdots &-1&-1\newline-1&-1&0&\cdots&-1&-1\newline\vdots&\vdots &\vdots&\ddots&\vdots&\vdots\newline-1& -1 & -1 &\cdots&0&-1\newline-1&-1&-1&\cdots&-1&0\newline v_1&v_2&v_3&\cdots&v_{k-1}&v_k\end{matrix}\right]$
那么用它自乘再预处理前 $k$ 个就可以矩乘了。
$code:$
Median
题面
考场
不知道是什么时候无意中看到了这道题的算法。但是没什么印象了，大概记得是二分吧。
所以首先我考虑在一个上面二分，然后每次在另一个上面 $lower_bound$ 出它的位置，加起来就可以知道它在合并之后的序列中的位置，复杂度就是 $O(n\log^2n).$
但是出题人好像卡了两个 $\log$ 的算法。。只有暴力分。
所以要更优秀的算法了。我们仍然考虑二分，但方式不同了。由上面的我们可以联想到，那前一半的数大概分布是一边多一边少的（废话。。），那么我们不就可以每一次扔掉多的那部分里面的一些吗？那么为了尽量优，我们可以考虑每次丢一半，这样就能做到一个 $\log$ 啦。具体而言是这样的：
假设我们现在还要选的数的个数是 $p$ ，那么我们可以分别在两个序列里面取第 $\large \frac{p}{2}$ 个，然后比较一下它们的值，可以发现那个更小的一定被那更多的一边覆盖住了，所以就可以丢掉它了。这样规模减少了一半。直到一遍被删完之后，就可以直接在另一边的里面找到答案了。
注意：上面说的更多一点其实是有问题的，仅用来理解这个算法的正确性。当一边的数分散在两极的时候，可能这边的少些，但是仍然要删它了。
出分：$100pt.$
$code: $
Sequence
题面
考场
我是怎么都没看出来它是一个积性函数。（因为在此之前我的认知是所有数都要有 $f(x)f(y)=f(xy).$）
然后写的爆搜。
出分： $10pt.$
正解
没错，这应该是一个积性函数。因为如果两个数互质，那么他们和 $B$ 的 $\gcd$ 一定是互不相关，因此由乘法原理，它们乘起来的总方案数就是答案。（也就是没有重叠的多余部分被计算了。）
那么看着这个数据范围，就可以试一下欧拉筛了。（前面模拟赛的时候考过学过。）
首先考虑 $f(p^c)$ 怎么做。因为最后贡献要和 $B$ 取 $\gcd$ 所以这个一定和 $B$ 中的 $p$ 个数有关。那么考虑 $B$ 质因数分解后 $p$ 的指数是 $k.$
那么对于 $A=p^c$ ，我们需要分两类讨论：$c>k$ 与 $c\le k.$ 对于第二类，我们可以枚举所有 $a$ 中最小的次数 $i\leq c$ 每一次用 $p$ 的次数大于等于 $i$ 的所有数的可能情况 $(c-i+1)^n$ 减去大于等于 $i+1$ 的情况就能得到至少有一个最小值次数是等于 $i$ 的情况了，而这些整个要乘上它们的贡献，也就是 $\gcd(a_1,\dots,a_n,~B)$ 也就是 $p^c$ 了。而对于第二类，因为总的次数不能超过 $k$ ，所以 $c$ 超过的部分是没有贡献的，或者说贡献仍然只有 $p^k$，所以我们只需要枚举到 $k$ ，超过的部分直接用一个表示超过取值 $c\to k$ 的整个式子就好了，它们的贡献上面也说了，就是 $p^k$。具体就是：
$\large\begin{equation}
\begin{aligned} f(p^c)=
\begin{cases}
c\leq k&&&\sum\limits_{i=1}^c ((c-i+1)^n-(c-i)^n)p^i.\\
c > k &&& \sum\limits_{i=1}^k ((c-i+1)^n-(c-i)^n)p^i+p^k(c-k)^n.
\end{cases}
\end{aligned}\end{equation}$
那么实现起来就是以前的欧拉筛模板，有一点区别的就是当 $i$ 是一个合数的最小质因子的时候，我们就要另外用他这个最小质因子的整个次数去乘了。