题解

数论 / 题解

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

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

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

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

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

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

More
  • 2023年3月10日
组合数学 / 题解

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

洛谷题库 P6031 Cards 加强版

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

这是某场模拟考试给出的部分分： SubtaskConstraintsPointsDependencies1n,m,k≤522k=123k≤5000101,24m≤1001015n≤k56k≤105101,2,37k≤5×106201,2,3,68411∼7 \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} （更多…）

More
  • 2023年1月31日
字符串 / 题解

CF356E – Xenia and String Problem – 题解

CodeForces CF356E – Xenia and String Problem

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

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

同时用归纳法可以证明，设一个 ww 阶 Gray string 的起始位置为 x+1x+1（其终到位置为 x+2w+1x+2^{w+1}），那么必然有 ∀k∈{0,1,⋯ ,w},sx+2k=sx+2k+2k+1=sx+2k+2×2k+1=⋯=sx+2k+(2w−k−1)2k+1∀i,j,0≤i<j≤w,sx+2i≠sx+2j \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} 成立。例如一个 33 阶 Gray string 可以被描述为 abacabadabacaba\mathtt{abacabadabacaba}。 （更多…）

More
  • 2023年1月5日
组合数学 / 题解

AtCoder AGC058D – Yet Another ABC String – 题解

AGC058D – Yet Another ABC String

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

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

More
  • 2022年12月16日
数据结构 / 题解

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

洛谷题库 P8868 [NOIP2022] 比赛

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

部分分

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

考虑枚举所有 O⁡(n2)\newcommand\bigO{\operatorname{O}}\bigO(n^2) 个区间，预先计算它们本身的答案。记 ga(l,r)={max⁡{ai∣l≤i≤r},(1≤l≤r≤n)0otherwisegb(l,r)={max⁡{bi∣l≤i≤r},(1≤l≤r≤n)0otherwise\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)=∑i=lrga(l,i)gb(l,i)s(l,r)=\sum_{i=l}^{r}g_a(l,i)g_b(l,i)，对于询问 [ql,qr][\text{ql},\text{qr}] 只需回答 ∑i=qlqrs(i,qr)\sum_{i=\text{ql}}^{\text{qr}}s(i,\text{qr}) 即可。

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

More
  • 2022年12月8日
OI / 组合数学 / 题解

CF1747E – List Generation – 题解

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

代数推导

转化为容斥模型

题目所给限制可以表述为，aa 和 bb 均为单调不降的序列，长度相等（记为 kk），且 a1=0,ak=n,b1=0,bk=m,∄i∈[2,k],ai=ai−1∧bi=bi−1a_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}。

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

More
  • 2022年12月1日
OI / 题解

AtCoder ARC149D – Simultaneous Sugoroku 简略题解

Atcoder ARC149D – Simultaneous Sugoroku

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

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

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

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

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

Submission #36155560 （更多…）

More
  • 2022年11月2日
OI / 数学 / 线性代数 / 题解

AtCoder ARC138D – Differ by K bits 简略题解

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

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

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

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

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

More
  • 2022年4月11日
OI / 数学 / 随记 / 题解

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

AtCoder ARC 134 C – The Majority

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

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

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

（更多…）

More
  • 2022年1月30日
OI / 图论 / 数学 / 数论 / 算法 / 题解

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

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

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

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

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

（更多…）

More
  • 2022年1月24日
成都外国语学校高二 OIer。喜欢搞些杂七杂八的小项目。常去骑车。复健中，脚力已不如前。

一言(ひとこと)

暫し空に祈りて 愛を断て

分类目录