2022 年 1 月刷题日志

UOJ50 链式反应

2022-01-14 | 题目链接 | </> 代码

ZAFU 2022.01.18 个人赛题解

请前往 ZAFU 2022.01.18 个人赛题解。

P3373 线段树 2

2022-01-27 | 题目链接 | </> 代码

P2023 维护序列

2022-01-27 | 题目链接 | </> 代码

P1531 I Hate It

2022-01-28 | 题目链接 | </> 代码

P5057 简单题

2022-01-28 | 题目链接 | </> 代码

给定一个 01 序列，有如下操作：

• 将区间 $[l,r]$ 上的数 01 翻转。
• 询问第 $i$ 个数的值。

区间操作，单点查询，很自然的想到了差分。

用异或或者加减代替翻转都可以，用树状数组维护。我选择了加减，这样询问时对 $2$ 取余即可。

P4588 数学计算

2022-01-28 | 题目链接 | </> 代码

初始是 $x=1$，我们每轮对 $x$ 做一个操作

• 将 $x$ 变为 $kx$，并输出 $xmodM$。
• 将 $x$ 变为 $x/k_i$，即取消第 $i$ 次操作，并输出 $xmodM$。

保证每个操作 1 的 $k$ 在操作 2 中至多被除一次。

$M$ 并不保证是质数，逆元可能不存在。

可以把操作序列看作一个乘积式，初始情况下全为 $1$。

• 操作 1 即是把第 $i$ 个数变为 $k$。
• 操作 2 即是把第 $i$ 个数变回 $1$。

修改结束后，询问所有数的乘积。单点修改，区间查询，标准的线段树。

因为只询问全体和，zkw 好写的多。

P1637 三元上升子序列

2022-01-28 | 题目链接 | </> 代码

给定一个序列，求其中三元上升子序列的个数

• 对于 $i,j,k$，若 $a_i<a_j<a_k$，则是一个满足要求的三元对。

考虑枚举中间的数 $j$，设其左边有 $a$ 个数比它小，右边有 $b$ 个数比它大，则中间为 $j$ 的三元对个数为 $ab$。

至此就和逆序对类似了，离散化后用树状数组即可。

P5431 乘法逆元 2

2022-01-28 | 题目链接 | </> 代码

给定 $n$ 个正整数 $\{a_i\}$ 和 $k$，求在模 $p$ 意义下的

$$\sum _{i=1}^n\frac{k^i}{a_i}modp$$

逐个求逆元是 $O(n\log p)$ 的，肯定会 T，需要想想别的办法。

批量求逆元的一个技巧，先求出 $a_i$ 的前缀积，然后求出全部积的逆元，再逐个往前推。即

$$(a_n{)}^{-1}=\left(\prod _{i=1}^{n-1}{a}_i\right){\left(\prod _{i=1}^n{a}_i\right)}^{-1}$$

显然，$\{a_n\}$ 中不能有 $0$。