24 暑假 diary

• 贵在坚持，难在坚持，成在坚持。

• 十年寒窗磨一剑，是非成败在今朝。

• 拼搏每一天，充实每一天，快乐每一天。

• 无才无以立足，不苦不能成才。

• 梦想，今日扬帆起航；前途，注定灿烂辉煌。

• 自信，是无尽智慧的凝聚。平淡，是成功路上的驿站。

• 遇到会做的题——仔细；遇到不会做的题——冷静。

• 不惜寸阴于今日，必留遗憾于明朝。

• 理想，是力量的泉源，智慧的摇篮，冲锋的战旗，斩棘的利剑。

• 高考得高分的秘诀就是少丢分。

7.28

前些日子在上 hb 的课，打算 29 号开始打下 MX 的。

那今天就摆摆摆了，就随手写了几道题。

7.29

上午模拟赛，打的爆炸了，取得了倒数前十的好成绩。

第一天就垫底，rp++ 了这下，但我真他妈不会啊。

然后就补题补了一下午+大半晚，谁叫你一题不会的来着。

A

考虑把平方内的式子化成 \(2m-2\sum_{i=1}^n\min(A_i,B_i)\)。

枚举 \(\sum\min(A_i,B_i)=s\)，那么此时序列的贡献就是 \((2m-2s)^2\)，对这种序列计数就可以了。

首先先对 \(s\) 隔板一下，把 \(s\) 分成 \(n\) 份且允许有空，方案是 \(\binom{n+s-1}{s}\)。

把 \(A_i\) 和 \(B_i\) 之间的关系分成 \(A_i>B_i\)，\(A_i=B_i\) 和 \(A_i<B_i\) 三种，枚举第一种位置有 \(x\) 个。

首先你要先在 \(A\) 里选出来 \(x\) 个，有 \(\binom{n}{x}\) 系数，然后你还要把 \(m-s\) 的和摊下来对吧，乘上 \(\binom{m-s-1}{x-1}\)。

最后就是你需要再把 \(m-s\) 的和摊在 \(B\) 的 \(n-x\) 个位置上，是 \(\binom{m-s+n-x-1}{m-s}\)。

复杂度是 \(O(nm)\) 的。

我草我场上真不会啊？？我草我场上真不会啊？？我草我场上真不会啊？？我草我场上真不会啊？？

B

考虑暴力做法直接设 \(f_{i,j}\) 表示 \(i\) 时刻 \(j\) 点的期望，对时间扫过去暴力转移即可得到 \(60\) 分。

显然地会发现这个 dp 可以写成矩阵乘法的形式，以为自己会了突然想起来输出的是异或和。

如果输出的是和可以直接倍增预处理转移矩阵的 \(2^k\) 然后做 \(m\) 次向量乘矩阵的快速幂即可（NOI2020D1T1），但是既然它让你输出的是异或和说明他肯定是要你每个时刻挨个求一遍的，所以应该放弃倍增这种做法。

考虑平衡复杂度，设置一个阈值 \(B\) 并每 \(B\) 个时刻一起做，处理出转移矩阵 \(M^k,k\in[1,B]\)，那么假设当前是在时刻 \(t\)，把 \(f\) 的一行看作是向量的话，时刻 \(t+k\) 的答案就是这个向量乘上 \(M^k\) 的第 \(n\) 项，而观察到求向量乘矩阵的某一项是 \(O(n)\) 的，所以这个做法很可能是可行的。

我们直接算一下看看，预处理 \(M^k\) 复杂度是 \(O(n^3B)\) 的，算每个时刻的答案是 \(O(\frac{T}{B}nT)=O(nT)\) 的，同时你最多连续算 \(B\) 次所以你需要完整乘上转移矩阵 \(\frac{T}{B}\) 次，这里是 \(O(\frac{T}{B}n^2)\) 的。观察一下可以直接取 \(B=175\)，然后过了。

理论最优是取 \(B=\sqrt{\frac{T}{n}}\)。

C

相比之下没那么神经的一道题，但是场上这题我是最不会的/cy。

记 \((x_i,y_i)\) 为第一轮走到第 \(i\) 步时走到的位置，容易发现走一轮起点到终点的坐标变化量是不变的，记为 \(dx\) 和 \(dy\)。

同时也容易观察到，第 \(k\) 轮时走到第 \(i\) 步的坐标和第 \(k-1\) 轮时走到第 \(i\) 步的坐标变化量也是 \(dx\) 和 \(dy\)，因为中间也正好差了一整轮，更形式地，第 \(k\) 轮第 \(i\) 步的坐标就是 \((x_i+(k-1)dx,y_i+(k-1)dy)\)。

所以说能走到的点在若干条以 \(\frac{dy}{dx}\) 为斜率的直线上，那你直接把第一轮的 \(|S|\) 个点按照所在的直线分类，每条直线内按照原来的横坐标排序根据差值就能算了。

复杂度大概是 \(O(|S|\log|S|)\)。

D

你也是道魔怔题。

考虑分块，先暴力处理出来初始的答案，去从区间覆盖这种操作入手。

修改时，散块内直接暴力改，考虑整块。因为块内的 \(b_i\) 是永远不会变的，所以设我们要把当前块修改成 \(x\)，那么只需要求出来最小的 \(\frac{xb_i}{\gcd^2(x,b_i)}\) 即可，如果知道 \(c_i\) 表示块内为 \(i\) 的倍数的 \(b\) 的最小值，那么可以枚举 \(x\) 的因数 \(d\)，用 \(\frac{dc_d}{d^2}=\frac{c_d}{d}\) 来更新答案。综上我们有了一个基于预处理的做法：先处理出来 \(c_{i,j}\) 表示第 \(i\) 个块内 \(j\) 的倍数的最小值，再根据刚才做法预处理出来 \(f_{i,j}\) 表示第 \(i\) 个块被覆盖成 \(j\) 的块内答案，修改时散块暴力整块直接查表打标记即可，查询是容易的。

有个很神经的地方是，修改时对散块暴力求 \(\gcd\) 多个 \(\log V\) 好像过不太去，要贺一个 \(O(V)-O(1)\) 的快速 \(\gcd\)……

块长直接取 \(B=\sqrt n\) 就能过，但是复杂度的瓶颈其实在预处理上，直接实现容易做到 \(O(\frac{n}{B}V\log V)\)，但是这个有点卡常，可以用类似埃筛的方式做到 \(O(\frac{n}{B}V\log\log V)\)。

我卡了一下午常/oh我卡了一下午常/oh我卡了一下午常/oh我卡了一下午常/oh