8.24 模拟赛
2024--梦熊&太戈--NOIP十三连测 #6【订正】 - 比赛 - 梦熊联盟 (mna.wang)
A. Alice 的数
有显然的 \(80\) 分。但是还是用两个小时冲到了 \(100\) 分。
做法比 std 复杂。
\(100+100+100\)。
题意
令 \(y^2\) 是距离 \(x\) 最近的完全平方数，若有不止一个最近的直接输出 \(\texttt{Game Over}\) 结束程序。定义 \(f(x) = (-1)^{y+1}y\)。
求 \(\sum_{i=l}^r f(i)\)。\(l, r \le 10^{18}\)。
做法
\(\texttt{Game Over}\) 是不可能的。
显然第一步差分。问题变成求 \([1, r]\) 的答案。
打表发现 \(f(x)\) 中 \(x\) 的系数形如：
\[\begin{matrix} x &: 1&2&3&4&5&6&7&8&9&10&11&12&13&14&15&16&17&18&19&20&\dots \\ (-1)^y&:[1&1]&[-1&-1&-1&-1]&[1&1&1&1&1&1]&[-1&-1&-1&-1&-1&-1&-1&-1]&\dots \end{matrix} \]为了方便我们称一个极长连续段为一段，例如表中 \([7, 12]\) 就是一段。
不难发现：
-
第奇数段中的数都是 \(1\)，第偶数段中的数都是 \(-1\)。
-
第 \(i\) 段的长度为 \(2i\)。
-
\(1 \sim n\) 段的长度和：
\[\sum_{i=1}^n 2i = 2\sum_{i=1}^ni = n(n+1) \] -
第 \(n\) 段的左端点与右端点下标：
左端点相当于前 \(1 \sim n - 1\) 段的长度和加一，右端点相当于 \(1 \sim n\) 段的长度和。分别为：
\[[n(n-1)+1,n(n+1)] \] -
第 \(n\) 段的下标和：
根据左右端点，用等差数列求和公式即可。
\[\dfrac{2n \times (n(n-1)+1+n(n+1))}2 = 2n^3+n \] -
前 \(1 \sim n\) 段的答案（乘上了 \((-1)^{i+1}\) 的系数后的）：
\[\sum_{i=1}^n(-1)^{i+1}(2n^3+n) = 2\times \sum_{i=1}^n(-1)^{i+1}i^3 + \sum_{i=1}^n(-1)^{i+1}i \]
所以我们可以计算 \(r\) 之前有多少完整段，并用上面说的计算这些段的答案。对于剩下的一个不完整的段，等差数列直接算即可。
现在的问题是如何快速计算：
\[\begin{matrix}\sum\limits_{i=1}^n(-1)^{i+1}i^3&\sum\limits_{i=1}^n(-1)^{i+1}i \end{matrix} \]后者是极易的。考虑计算前者：
\[s_n = 1^3-2^3+3^3-4^3+\dots+(-1)^{n+1}i^3 \]注意到：
\[\begin{bmatrix} s_{n-1} & n^3 & n^2 & i & 1 \end{bmatrix} \times \begin{bmatrix} 1 & 0 & 0 & 0 & 0 \\ 1 & -1 & 0 & 0 & 0 \\ 0 & -3 & -1 & 0 & 0 \\ 0 & -3 & -2 & -1 & 0 \\ 0 & -1 & -1 & -1 & -1 \end{bmatrix} =\begin{bmatrix} s_n & -(n+1)^3 & -(n+1)^2 & -(n + 1) & -1 \end{bmatrix} \]矩阵加速即可。
B. Bob 的图
\(70+55+100\)。
很好的题。会计算答案，会 DAG 部分分，拼起来就是正解，为啥还不会做呢？
做法
给定一张带边权的有向图。令 \(n_i\) 表示 \(1 \rightsquigarrow i\) 的最短路方案数，\(d_{i, k}\) 表示第 \(k\) 条 \(1 \rightsquigarrow i\) 的最短路经过的边数。求：
\[\sum_{i=1}^n\sum_{j=1}^n\sum_{k=j+1}^n d_{i,j}\times d_{i,k} \]取模 1e9 + 7。
做法
首先
\[\sum_{j=1}^n\sum_{k=j+1}^n d_{i,j}\times d_{i,k} = \dfrac{\left(\sum_{j=1}^nd_{i,j}\right)^2-\sum_{j=1}^nd_{i,j}^2}2 \]所以我们要维护的是 \(1 \rightsquigarrow i\) 的所有最短路的边数和，以及平方和。
建最短路 DAG。即保留所有满足 \(dis_u = dis_v+w_{u,v}\) 的边 \((u, v)\)。其中 \(dis_u\) 是 \(1 \rightsquigarrow i\) 的最短路，用 Dijkstra 预处理。
那么在原图中求 \(1 \rightsquigarrow i\) 的所有最短路的边数和以及平方和，等价于在新图中求 \(1 \rightsquigarrow i\) 的所有路径的边数和以及平方和。
极易！令 \(f(i, u)\) 表示 \(1 \rightsquigarrow u\) 的所有路径的边数的 \(i\) 次方和。其中 \(0 \le i \le 2\)。拓扑排序转移（边 \(u \to v\)）：
\[f(0,u) \to f(0,v) \\ f(0,u)+(1,u) \to f(1, v) \\ f(0,u)+2f(1,u)+f(2,u)\to f(2,v) \]C. 维护整数列
\([60,80]+0+100\)。
数据是大海。
负数取模错了导致 \(100 \to 0\)。
我都能构造数据卡掉我自己但是满分了。
题意
维护数据结构，支持单点修，求区间和，求区间平方和，将区间所有数除以 \(p\) 下取整。
不保证任何值非负（除 \(n, m\) 之类的）。保证 \(p \ne 0\)。这里下取整指 C++ 中的 floor() 函数。
做法
没有负数是大水题。
除以 \(p = 1\) 相当于啥也没做，除以 \(p = -1\) 相当于区间取反（显然区间取反不会影响区间平方和）。对于除以其它的数 \(|p|\ge 2\)，最多除以 \(\log\) 次后就会变成 \(0\)。
普通的修改暴力。如果这个线段树节点所代表的区间内的数都是 \(0\) 则不同修改。
D. 大头问题
\(50+55+100\)。
还在调。