MOCK NOIP 20221018 日志

堪堪能接受的一场。前两题一个半小时左右做完，后两题实在没什么思路，打完所有可能的暴力之后跑路了。

他们告诉我题目名称可以从上到下连起来读。

一句话题解

A – （种）菜

可以发现，假若同时有 $\newcommand{\bigO}{\operatorname{O}}a_i,a_{i+1}$ 和 $a_{i+1},a_{i+2}$ 都可合并，则取 $a_i, a_{i+2}$ 中任意一个合并之后，质因数集合总是变为原来的超集，另外一项仍可合并。

故而可以贪心合并所有合法的邻项，最终检查是否仅剩一项即可。注意到 $[1,700]$ 仅含 $125$ 个质因数，故可以用 std::bitset 保存每一项的质因子集合。复杂度 $O(\frac{128n}{\omega})$。赛时竟然还开了数组保存每个质因子的实际指数！

B – （养）狗

观察到标记为 $\texttt{L,R}$ 的狗只可能与同一行内 $\texttt{R,L}$ 的狗交友；$\texttt{U,D}$ 亦然。每一行、每一列之间的方案是两两独立的。分别对它们计数。

以同行内的 $\texttt{L,R}$ 为例。对于每一个 $\texttt{R}$，我们试图向左为其匹配一个 $\texttt{L}$，亦或不匹配。若左侧在匹配后剩余 $k$ 个 $\texttt{L}$，则这条狗有 $k$ 种匹配方法。故而记 $f(i,k),g(i,k)$ 表示在考虑前 $i$ 条狗（不分类别）后剩 $k$ 条标 $\texttt{L}$ 的狗的匹配方案数和所有方案的权值总和，转移分两类讨论即可。

时间复杂度 $\operatorname{O}(n^3)$。

C – 可

赛时想起 CF1734F – Zeros and Ones 含（两个数的和的）进位的二进制数位 DP 的一种方法：从高往低考虑每一位，同时记录“其和的二进制表示的末尾有多少个连续的 $1$”。

又想起可以从低位向高位填写，保存向更高位进位的信息；若有上限，则记录“当前是否有某一位大于上限的对应位且其更高位不小于上限对应位”。一个例子是 NOIP 2021 B – 数列，还有某到模拟赛题目，可惜我忘记了。不过这道题有 $k\leq 20, \lg x\leq 10^4)$，还是十进制表示（这意味着要记录多达 $180$ 种进位情况），更不说需要枚举下一位填写的数字以计算 $f(x)$，运行时间不可接受。

若 $kx\leq 10^4$（$\text{20 pts}$ 做法）

有一经典问题：带限制的非负/正整数多元方程解个数。求取方程 $$x_1+x_2+\cdots+x_n=m\quad(\forall i \in \{1,\cdots,n\},x_i\in \mathbb{Z},x_i\in[0, d]$$的解的个数。由容斥原理，它等于 $$g(n,m)=\sum_{k=0}^{n}(-1)^k\binom{n}{k}\binom{m-k(d+1)+n-1}{n-1}$$

我们可在 $\operatorname{O}(\lg x)$ 的时间内轻松计算 $f(x)$，故枚举 $\sum_{i=1}^{k}x_i=s$，计算 $f(s)g(s,k)$ 即可。

正解

我本以为会有更高明的办法作数位 DP，结果还是太单纯了。

正解竟然是上述解法的优化。考虑以下式子： $$\begin{aligned} &\sum_{s=0}^{kx}f(s)g(s,k)\\ =&\sum_{i=0}^{k}(-1)^i\binom{k}{i}\sum_{s=0}^{kx}f(s)\binom{s-i(x+1)+k-1}{k-1}\\ =&\sum_{i=0}^{k}(-1)^i\binom{k}{i}\sum_{s=0}^{kx}f(s)\frac{[s-i(x+1)+k-1]!}{(k-1)![s-i(x+1)]!}\\ =&\sum_{i=0}^{k}\frac{(-1)^ik}{(k-i)!i!}\sum_{s=0}^{kx}f(s)[s-i(x+1)+k-1]^{\underline{k-1}}\quad\text{（将阶乘转写为下降幂）}\\ =&\sum_{i=0}^{k}\frac{(-1)^ik}{(k-i)!i!}\sum_{s={\color{red}i(x+1)}}^{kx}f(s)\sum_{l=0}^{k-1}\begin{bmatrix}k-1\\i\end{bmatrix}(-1)^{k-l-1}[s-i(x+1)+k-1]^l\quad\text{（}\href{https://oi-wiki.org//math/combinatorics/stirling/# =&\sum_{i=0}^{k}\frac{(-1)^ik}{(k-i)!i!}\sum_{l=0}^{k-1}\begin{bmatrix}k-1\\i\end{bmatrix}(-1)^{k-l-1}\sum_{s={\color{red}i(x+1)}}^{kx}f(s)(s+\alpha_i)^l,\quad \alpha_i=-i(x+1)+k-1\quad(*)\\ =&\sum_{i=0}^{k}\frac{(-1)^ik}{(k-i)!i!}\sum_{l=0}^{k-1}\begin{bmatrix}k-1\\i\end{bmatrix}(-1)^{k-l-1}\sum_{s={\color{red}i(x+1)}}^{kx}f(s)\sum_{p=0}^{l}\binom{l}{p}s^p\alpha_i^{l-p}\\ =&\sum_{i=0}^{k}\frac{(-1)^ik}{(k-i)!i!}\sum_{l=0}^{k-1}\begin{bmatrix}k-1\\i\end{bmatrix}(-1)^{k-l-1}\sum_{p=0}^{l}\binom{l}{p}\alpha_i^{l-p}\sum_{s={\color{red}i(x+1)}}^{kx}f(s)s^p\\ =&\sum_{i=0}^{k}\frac{(-1)^ik}{(k-i)!i!}\sum_{l=0}^{k-1}\begin{bmatrix}k-1\\i\end{bmatrix}(-1)^{k-l-1}\sum_{p=0}^{l}\binom{l}{p}\alpha_i^{l-p}\left(\boxed{\sum_{s=0}^{kx}f(s)s^p-\sum_{s=0}^{{\color{red}i(x+1)-1}}f(s)s^p}\right) \end{aligned}$$

若设 $h(n,p)=\sum_{s=0}^{n}f(s)s^p$，则框内部分等于 $h(kx,p)-h\left(i(x+1)-1,p\right)$。

$h(n,p)$ 的计算可以通过数位 DP 实现。设下一位填写 $c$，$f(x)\rightarrow f(10x+c), x^p\rightarrow (10x+c)^p$ 的贡献均可用二项式系数变成线性，同时转移 $h(?,0\cdots k-1)$ 即可。至于 $i(x+1)-1$ 的真实数位情况，可以应用 $20$ 次高精度加法实现。

由于时限较紧，转移 $h$ 时需要统一计算 $c=1,\cdots,9$ 以及 $c=0$（$f(0)=1$）的贡献而不能枚举，它是一个可以打表存储的小范围等幂求和式。

时间复杂度 $\operatorname{O}(\lg xk^3)$。

正解 – 部分优化

发现 $(*)$ 式中 $\alpha_i$ 是一常数，于是我们暴力将其展开，能够得到一 $k-1$ 次多项式。再应用类似过程计算即可。这玩意可比斯特林数方便多了。

D – 爱

上题解吧。

考虑 $f(p^c)=p^{114514c}\left(\frac{(p+1)^{1919810}}{p^{114514}}\right)^{\max(c-2,0)}$。

两部分是独⽴的，我们可以先求出第一个因数的乘积，再乘上第⼆个的乘积。

⾸先我们对于质因⼦ $p\leq 1000$，每⼀个开⼀个数据结构维护和。可以使用分块，$\operatorname{O}(\sqrt{n})$ 更改 $\operatorname{O}(1)$ 查询。

接下来剩下的每个数要么是质数，要么是 $1$。考虑没有修改操作，我们可以把所有质因子为 $p>1000$ 的位置拎出来。记这些位置为 $a_1,a_2,\cdots, a_k$。然后加入 $k-2$ 条线段 $[a_i,a_{i+2}],\forall i\in \{1,\cdots,k\}$，权值为 $\frac{(p+1)^{1919810}}{p^{114514}}$，则第二部分的乘积便是 $[l,r]$ 完整包含的所有线段的权值积。模拟可以发现，若从位置集合中删去/加入某个点，则发生变化的线段条数最多为 $5$。故这是一个带修改的二维偏序问题，可以用数据结构维护。

若采用树套树，需小心常数和空间问题，总时间复杂度为超大常数的 $\bigO(q\log^2 n)$。担心空间不够，我采用线段树套平衡树实现，可惜仅获得 $\text{80 pts}$。

注意到在同一时刻，每一位置 $i$ 最多分别作为一条线段的左端点和另一条线段的右端点。同时我们查询的是区间积，$1019260817$ 是一质数，故乘法在 $\mathbb{Z}/p$ 上存在逆运算，可以快速撤销更改。于是将整个序列分块，记块长为 $S$，则我们查询 $[l,r]$ 内线段权值积时，记块 $j,j+1,\cdots,k$ 均完整包含在 $[l,r]$ 内。使用树状数组维护左端点在块 $s$，右端点在块 $t\leq s$ 内的所有线段的权值前缀积。则在 $s\in[j,k]$ 块内查询 $[s,k]$ 的数据，在散块内暴力即可。删除（乘权值逆元）和插入一条线段的复杂度为 $\bigO(\log \frac{n}{S})$，单次查询复杂度为 $\bigO\left(\frac{n}{S}\log\frac{n}{S}+S\right)$，求导可以得到其最小值点在 $S=\sqrt{n\log n}$ 时取到（实际实现时可以更激进地减少块长）。这是目前除了 k-D Tree 跑得最快的解法。