数据比较强的 BSGS 题,很多细节都卡到了√ 题目描述 小 W 喜欢读书,尤其喜欢读《约翰克里斯朵夫》。最近小 W 准备读一本新书,这本书一共有 $P$ 页,页码范围为 $0 \cdots P-1$。 小 W 很忙,所以...
BSGS/exBSGS 学习笔记【同余】
〇、前言 BSGS 是用来求形如 $a^x\equiv b\pmod p$ 的最小非负整数解的算法。 当 $\gcd(a,p)=1$ 时可以直接使用 BSGS,当 $\gcd(a,p)\ne 1$ 时需要用到 exBSGS 进行转化。 参考资料: PoPoQQQ 《原根与指标》...
洛谷 P4169 天使玩偶 / SJY 摆棋子 题解【k-d tree】【估价】
k-d tree 貌似总是会被卡掉一两个点…不过 OI 赛制还是很好的 题目描述 Ayu 在七年前曾经收到过一个天使玩偶,当时她把它当作时间囊埋在了地下。而七年后 的今天,Ayu 却忘了她把天使玩偶埋在了哪里,所...
bzoj 2683/4066 简单题 题解 k-d tree 简要讲解【k-d tree】
题目描述 你有一个 $N\times N$ 的棋盘,每个格子内有一个整数,初始时的时候全部为 $0$,现在需要维护两种操作: 命令 参数限制 内容 $1\ x\ y\ A$ $1\le ...
CTS&APIO2019 春眠记【游记】
又到了春困的时候。 ↓建议搭配配乐食用(如果在机房还是算了吧 [aplayer apid="3795"][/aplayer] CTS 部分 Day -6 过审了。 Day -2 PKUSC/THUSC 可以报名了。整了一上午终于把资料弄进去了。 如果这波过...
CF1163E Magical Permutation 题解【线性基】【递归】【构造】
首先恭喜 xht37 喜提本场 rk1。 考场上想到线性基了不会构造…貌似还有一些别的细节 Description Kuro has just learned about permutations and he is really excited to create a new permutation typ...
洛谷 P4336 [SHOI2016]黑暗前的幻想乡 题解【矩阵树定理】【容斥】
矩阵树定理明明只是个记结论的东西对吧..(大雾 题目描述 四年一度的幻想乡大选开始了,最近幻想乡最大的问题是很多来历不明的妖怪涌入了幻想乡,扰乱了幻想乡昔日的秩序。但是幻想乡的建制派妖怪(人类...
洛谷 P5284 [十二省联考2019]字符串问题 题解【后缀自动机】【倍增】【拓扑排序】
考场上唯一一道弃掉的题。看来 SAM 还是挺好玩的 题目背景 Yazid 和 Tiffany 喜欢字符串问题。在这里,我们将给你介绍一些关于字符串的基本概念。 对于一个字符串 $S$,我们定义 $|S|$ 表示 $S$ 的...
51nod 1600 Simple KMP【KMP】【SAM】【树链剖分】
利用了 KMP 性质和 SAM 这一“数据结构”的特点并进行了动态维护。 题目描述 对于一个字符串 $S$,我们定义 $fail[i]$,表示最大的 $x$ 使得 $S[1..x]=S[i-x+1..i]$,满足 $(x<i)$。 显然对于一个...
黑白棋 题解【平衡树】【线段树】【前缀和】
数据结构好题。学会了平衡树代替权值线段树(雾 题目描述 黑白棋的棋盘有 $N$ 行 $M$ 列,而且这 $N\times M$ 个位置上全部都放好了棋。棋的正面为白色,反面为黑色。我给这个棋盘的每行每列都施展了一...