Contents
前言
新年快乐！终于活过 2020 年了。
WC2021 GZOI2021 NOI2021（如果有可能的话）rp++
学习内容
- 欧拉函数
- (ex)BSGS
- 矩阵乘法的应用
- 高斯消元
- 基础分块
- 基础线性代数
- 数位 dp
- 复杂度分析
- 狄利克雷卷积
- 莫比乌斯反演
- 杜教筛
- FFT
做题记录
21/01/01
- EOJ monthly 2020.01 A+C+E rk80
- P1072 [NOIP2009 提高组] Hankson 的趣味题
需要特别注意处理 a_0,a_1,b_0,b_1>\sqrt n 的情况
- P2158 [SDOI2008]仪仗队
设左下角 (0, 0)，右上角 (n-1, n – 1)。抛开 (1,0)(0,1)(1,1) 三个点，发现能看到的关于对角线对称，考虑一半即可。这一半就是求 1\le x\lt y 且 x \perp y 的 (x,y) 对数，发现对于每个 y 来说这样的 x 对数即为 \varphi(y)。
答案为 \displaystyle3 + 2\sum_{i=2}^{n-1}\varphi(i)，特判 n = 1 的情况
21/01/06
- POJ3696 The Luckiest number
欧拉定理的推论 https://imyangty.com/oi/1280
- P3846 [TJOI2007] 可爱的质数/【模板】BSGS
BSGS
21/01/07
- P4861 按钮
求满足 k^x\equiv 1\pmod m 的最小正整数 x。由裴蜀定理可得有解的充要条件是 \gcd(k, m) = 1，所以直接 BSGS
- P2485 [SDOI2011]计算器
快速幂取模 + exgcd + BSGS 综合题
21/01/09
- P4195 【模板】扩展BSGS/SP3105 MOD – Power Modulo Inverted
exBSGS
- CF1063B Labyrinth
双端队列优化 01bfs
- CF786B Legacy
线段树优化建图模板
21/01/13
- BZOJ2973 石子游戏
构造转移矩阵，矩阵乘法
21/01/14
- P3389 【模板】高斯消元法
高斯消元
- LOJ6208 树上询问
- P4035 [JSOI2008]球形空间产生器
推式子，二次项消去后高斯消元
21/01/15
- LOJ#6277. 数列分块入门 1
区间修改单点求值
- LOJ#6278. 数列分块入门 2
区间修改区间询问某数排名
- P3372 【模板】线段树 1
分块重写
21/01/16
- CF149D Coloring Brackets
区间 dp（记忆化搜索）， f(i, j, k_1, k_2) 为合法序列 [i,j]，两端状态 k_1, k_2，需注意合法序列两端未必就是匹配的，所以之前定义 f(i, j, k) 是错误的
- CF242E XOR on Segment
区间 xor 区间求和，按位拆分方便处理区间 xor，对于每一位都建一棵线段树，xor 就是集体取反。
21/01/17
- CF607A Chain Reaction
线性 dp，f_i 为从位置 i 开始激活最多保留的激光塔个数
- P1005 [NOIP2007 提高组] 矩阵取数游戏
很水的区间dp，难点高精，int128 过之
- LOJ#6279. 数列分块入门 3
区间修改区间询问某数前驱
21/01/21
- LOJ#6280. 数列分块入门 4
区间修改区间查询
- LOJ#6281. 数列分块入门 5
区间开根区间查询
21/01/23
- POJ1830 开关问题
高斯消元求解 xor 方程组
- P1102 A-B 数对
std::map 或二分
- LOJ#6282. 数列分块入门 6
单点插入单点查询（块状链表）
- LOJ#6283. 数列分块入门 7
区间乘区间加单点查询
- LOJ#6284. 数列分块入门 8
区间查询某数出现个数并赋值
- P4168 [Violet]蒲公英
强制在线区间众数
- LOJ#6285. 数列分块入门 9
区间众数
21/01/24
- P4127 [AHOI2009]同类分布
- P2657 [SCOI2009] windy 数
数位 dp
21/01/25
- Codeforces Round #697 (Div. 3)
A+B+C+E，是否 fst 未知
21/01/26
- Codeforces Round #697 (Div. 3)
没有 fst，A+B+C+E
- P3455 [POI2007]ZAP-Queries
- P2522 [HAOI2011]Problem b
- P2257 YY的GCD
莫比乌斯反演
21/01/27
- P4213 【模板】杜教筛（Sum）
杜教筛
21/01/28
- Codeforces Round #698 (Div. 2)
A + B，菜的我直接爬
21/01/29
- P3803 【模板】多项式乘法（FFT）
FFT 板子
- P1919 【模板】A*B Problem升级版（FFT快速傅里叶）
FFT 实现高精度乘法
- Educational Codeforces Round 103
菜的抠脚依旧 A + B，C 没调出来
21/01/30
- P3338 [ZJOI2014]力
转化式子之后使用 FFT
- P3312 [SDOI2014]数表
莫反 + 树状数组，比较巧妙
- P3377 【模板】左偏树（可并堆）
左偏树模板
21/01/31
- P3723 [AH2017/HNOI2017]礼物
FFT/NTT 加速卷积
- P2224 [HNOI2001]产品加工
奇葩的状态定义：https://imyangty.com/oi/1298
留言