NGC5457's Site

分类： 题解

  • 2023 NOI 春季测试 T2 – 幂次 简略题解

    洛谷题库 P9118 [春季测试 2023] 幂次

    我们有非常易于理解的暴力解法：直接对于 $b=3,4\cdots$，求出所有可以当作底数的 $a$，计算 $a^b$ 后放入数据结构/排序去重；特别处理 $b=2$ 的情况即可。在此不再赘述。

    不过，我们注意到若有正整数 $x$，满足 $x>1,x=a_0^{b_0}\ \ (a_0,b_0\in \mathbb N)$，且 $\forall a,b\in\mathbb N,a_0\neq a^b$（即底数 $a_0$ 不可再开根），那么 $\forall b,b\mid b_0,x=(a_0^{b_0/b})^b$。这意味着假如不去重地暴力添加 $\lfloor\sqrt[b]{n}\rfloor$ 到答案中，上文中 $x$ 将被算 $|\{b\mid b_0\equiv 0\pmod b\}|$ 次。

    于是这就变成莫反的模板题了：记 $g(b)$ 表示“能被 $a^b$ 表出的 $x$ 之数量”，$f(b_0)$ 表示“恰能被 $x=a_0^{b_0}$ 表出，不可被 $x=a^b,b<b_0$ 表出的 $x$ 的数量”。易得 $g(b)=\sum_{b\mid b_0}f(b_0)$，故 $f(b_0)=\sum_{b_0\mid b}g(b)\mu(b/b_0)$。显然，当 $b>\log_2 n$ 时仅有 $a=1$ 满足 $a^b\leq n$，故我们只需计算 $\lfloor\log_2 n\rfloor$ 个 $b$，最后特判 $a=1$。预处理出 $\mu$ 的值，暴力求取反演式，复杂度为 $\operatorname{O}(\log^2 n)$。

    其实并不需要这么麻烦。我们根本不需要反演：根据 $g(b)=\sum_{b\mid b_0}f(b_0)$，假若 $\forall b_0,b_0>b,f(b_0)$ 都已经计算完成，那么我们直接得到 $f(b)=g(b)-\sum_{b\mid b_0,b_0>b}f(b_0)$。由 $b$ 从大往小计算即可，复杂度相同。

  • 洛谷题库 P6031 Cards 加强版 – 题解与思路重现

    洛谷题库 P6031 Cards 加强版

    对于每一轮对局的 $m!$ 种排列，对于编号为 $a$ 的牌，恒有 $(m-1)!$ 种是以牌 $a$ 为首的。因此一轮可以归为 $m$ 种情况，首张为王牌的概率为 $\frac{1}{m}$。

    这是某场模拟考试给出的部分分：
    $$
    \begin{array}{cccc}
    \text{Subtask}&\text{Constraints}&\text{Points}&\text{Dependencies}\\ \hline
    1&n,m,k\leq 5&2&\\
    2&k=1&2&\\
    3&k\leq 5000&10&1,2\\
    4&m\leq 100&10&1\\
    5&n\leq k&5&\\
    6&k\leq 10^5&10&1,2,3\\
    7&k\leq 5\times 10^6&20&1,2,3,6\\
    8&&41&1\sim 7
    \end{array}
    $$ （更多…）

  • CF356E – Xenia and String Problem – 题解

    CodeForces CF356E – Xenia and String Problem

    这是一种不需要任何数据结构和处理字符串的工具，但细节繁多的做法。

    设全串为 $s_{1\dots n}$。不难发现，Gray string 的串长必然是 $2^w-1\quad (w\geq 1)$ 的形式。若其长为 $2^w-1$，我们称其为 $w-1$ 阶 Gray string。

    同时用归纳法可以证明，设一个 $w$ 阶 Gray string 的起始位置为 $x+1$（其终到位置为 $x+2^{w+1}$），那么必然有
    $$
    \forall k\in\{0,1,\cdots,w\},s_{x+2^k}=s_{x+2^k+2^{k+1}}=s_{x+2^k+2\times 2^{k+1}}=\cdots=s_{x+2^k+(2^{w-k}-1)2^{k+1}}\\
    \forall i,j,0\leq i<j\leq w,s_{x+2^i}\neq s_{x+2^j}
    $$
    成立。例如一个 $3$ 阶 Gray string 可以被描述为 $\mathtt{abacabadabacaba}$。 （更多…）

  • AtCoder AGC058D – Yet Another ABC String – 题解

    AGC058D – Yet Another ABC String

    将 $\mathtt{A,B,C}$ 换成 $0,1,2$。记 $a,b,c$ 是题面中 $\mathtt{A,B,C}$ 的数量，$n=a+b+c$。我们称位置 $i$ 不合法，当且仅当 $S_{i-2}+2\equiv S_{i-1}+1\equiv S_i\pmod 3$。将其视为两条边 $(i-2,i-1),(i-1,i)$，那么所有不合法的位置造成的连边将会形成若干条链。

    考虑容斥。直接钦定指定数量的位置不合法，其方案是难以计算的。又因为容斥系数是 $(-1)^c$，$c$ 为钦定的非法位置数量，那么将整个串分成若干个部分分别计算方案，带上容斥系数相乘后累加，结果不变。故而尝试从上文的链入手：易得对于固定长度的一条链，能够连成它的非法位置集合不变。设 $f(l,0)$ 表示“大小为偶数，且能够连成长度恰为 $l$ 的链”的非法位置集合数量；$f(l,1)$ 则是大小为奇数。染色方案与位置集合方案是独立的；则设整个串按顺序被分成了链 $(l_1,l_2,\cdots,l_s)$（此处的“链”长度均不小于 $3$），答案即为
    $$\sum_{(l_1,\cdots,l_s)}\operatorname{染色方案数}\left((l_1,\cdots,l_s)\right)\prod_{i=1}^s\left((-1)f(l_i,1)+f(l_i,0)\right)$$ （更多…）

  • NOIP 2022 T4 – 比赛 (match) – 题解

    洛谷题库 P8868 [NOIP2022] 比赛

    本文记号可能稍显凌乱，但都能在题面或者前文中找到定义。

    部分分

    $\text{20 pts}$ – $n,Q\leq 3000$

    考虑枚举所有 $\newcommand\bigO{\operatorname{O}}\bigO(n^2)$ 个区间，预先计算它们本身的答案。记
    $$\begin{aligned}g_a(l,r)&=\begin{cases}\max\{a_i\mid l\leq i\leq r\},&(1\leq l\leq r\leq n)\\0&\text{otherwise}\end{cases}\\g_b(l,r)&=\begin{cases}\max\{b_i\mid l\leq i\leq r\},&(1\leq l\leq r\leq n)\\0&\text{otherwise}\end{cases}\end{aligned}$$
    则做前缀和 $s(l,r)=\sum_{i=l}^{r}g_a(l,i)g_b(l,i)$，对于询问 $[\text{ql},\text{qr}]$ 只需回答 $\sum_{i=\text{ql}}^{\text{qr}}s(i,\text{qr})$ 即可。

    令 $n, Q$ 同阶，时空复杂度 $\bigO(n^2)$。 （更多…）

  • CF1747E – List Generation – 题解

    这道破题拖了我整整一天。

    代数推导

    转化为容斥模型

    题目所给限制可以表述为，$a$ 和 $b$ 均为单调不降的序列，长度相等（记为 $k$），且 $a_1=0,a_k=n,b_1=0,b_k=m,\nexists i\in[2,k],a_i=a_{i-1}\land b_i=b_{i-1}$。

    考虑差分序列 ${a_i}’=a_i-a_{i-1}\quad(i\in[2,k])$，${b_i}’$ 同理，它与原序列形成双射。于是不存在 ${a_i}’={b_i}’=0$ 的差分序列合法。考虑 $\sum_{i=2}^{k}{a_i}’=n$，也就是和为 $n$ 的 $k-1$ 元线性方程组的一组非负整数解；$b’$ 同理。容易计算“钦定至少有 $c$ 个位置不合法”的方案数——利用容斥原理即可得到长为 $k$ 的合法序列对个数为
    $$\sum_{c=0}^{k-2}\binom{k-1}{c}\binom{n+(k-1)-1-c}{(k-1)-1-c}\binom{m+(k-1)-1-c}{(k-1)-1-c}(-1)^c$$ 答案累加上式结果 $\times k$。 （更多…）

  • AtCoder ARC149D – Simultaneous Sugoroku 简略题解

    Atcoder ARC149D – Simultaneous Sugoroku

    官方题解做法是线性的，在此不再赘述。

    考虑对于纸片 $X=1,2,\cdots,\max\{X_i\}$ 分别计算答案。每次暴力枚举显然不可取，但假若我们知晓对于 $X$，在 $i=0,1,\cdots,M$ 次操作以后纸片在数轴上的坐标 $x_0=X,x_1,\cdots,x_m$，其中 $\text{pos}$ 是最小的取到 $x_\text{pos}=-1$ 的位置，则对于 ${x_0}’=X’=X+1$：

    • 如果 $\text{pos}$ 不存在，则所有坐标整体向数轴正半轴平移 $1$ 单位；
    • 否则，$\text{pos}$ 就将是起始点为 $X’$ 的纸片首次到达 $0$ 点的位置，也即题目所求。所有小于 $\text{pos}$ 的坐标仍向正半轴平移 $1$ 单位；而 $\geq \text{pos}$ 的坐标，由于偏移量 $D_i$ 符号翻转，则有 ${x_i}’-{x_{i-1}}’=-(x_i-x_{i-1})$。依次考虑每一坐标，就会得到 ${x_i}’=1-x_i,\forall \text{pos}\leq i\leq m$。
      （这里认为当 $x_\text{pos}=0$ 时仍然继续执行操作。维护 $\geq\text{pos}$ 的坐标位置是为了计算 $X”>X’$ 的答案。）

    这是可以用区间树维护的：我们想要快速求出全局非正数最大值以及首次取到该最大值的位置，同时支持全局加 $1$、后缀所有数符号翻转 （$\times -1$）。那么同时维护区间非负数最大值、正数最小值以及首次取到他们的位置，采用延迟标记更新（两种操作对于前述信息是具有结合律的，形成幺半群）即可。

    时间复杂度 $\operatorname{O}(\max\{X_i\}\log M)$，常数一般。

    Submission #36155560 （更多…）

  • AtCoder ARC138D – Differ by K bits 简略题解

    考虑这个排列是怎样生成的。转述一下题意，可以发现，$\operatorname{popcount}(P_i \oplus P_{i+1 \mod {2^n}})=K$，也即全集$\text{msk}=2^N-1$的一个大小为$K$的子集。

    由于这是一个环排列，我们不妨令$P_0=0$。这样一来，$P_i=\operatorname{\bigoplus}\limits_{j=1}^{i}S_j, |S_j|=K$。结合上文可知，这是一个相邻元素二进制位恰相差$K$位的格雷码问题。有$K=1$时，满足条件的$S_j$恰有$N$个，也就是$N$位格雷码。

    考虑推广。我们发现，如果按照类格雷码的方式生成排列，则所有的$S_j$应构成异或空间，其大小应当恰为$2^N$，并且由线性空间知识可以得到，该线性空间的秩（基的大小）应当恰为$N$。这恰好符合$N$位格雷码的构造。因此，只要满足上述条件，就一定能够生成符合题意的排列。

    可以证明，除了$2\mid K \lor (K=N \land N>1)$以外，总是有满足条件的线性空间生成的。

    下述解法的时间复杂度$\operatorname{O}\left(\dbinom{N}{K}+2^N\right)$。 （更多…）

  • AtCoder ARC134C – The Majority – 简略题解与思路重现

    AtCoder ARC 134 C – The Majority

    如此ruzhi的一道题目竟花去两小时有余，比赛结束也没写出来，实在惭愧。

    拿到题目，很快想到一种DP：令$f(i, j, k)$表示“考虑到第$i$个盒子，第$1$种小球用去$j$个，第$2, 3, \dots, n$种小球用去$k$个”的方案数。容易转移。

    然后发现$a_i$是$10^9$级别。同时题目告诉我们，相同类别小球无法区分，所以要是上述做法正确，为什么要分别给出$a_2, a_3, \dots$呢？如何在转移时确保每一种小球的使用次数正确？立刻想到正解与$\mathrm{O}(a_i)$基本无关。

    （更多…）

  • AtCoder ABC236G – Good Vertices – 题解 – 矩阵乘法优化DP

    昨晚参与AtCoder ABC 236时认为G题似乎可做，直到看到数据范围才发现事情没有那么简单。

    由于最近学习离线数据结构，又见识过一道题意接近的题目，故想到整体二分，二分每一个节点第一次能恰好经过$L$条边到达的时间，然后考虑DP求解。设计状态$f(i, x)$表示在该图上经过恰好$i$次转移能否到达点$x$。但很快发现每一次二分时均要重新在图上运行DP，时间复杂度无法承受。况且DP递推转移的次数$L$高达$10^9$，甚至不可能是线性的复杂度。

    今天查看题解，发现有几个重要的，从未考虑过的trick：

    1. 既然要求能够经恰好$L$次转移到达的最早的时间点，则我们将每条边的边权$w$设为其加入图中的时间，则可以转化成恰有$L$条边的最小瓶颈路。
    2. 发现$L$很大，所以考虑通过矩阵乘法加速递推，也即所谓倍增优化DP的一种。

    （更多…）