数学杂项
在《具体数学》一书和其他的什么地方找到的一些不知道放在哪的小trick和感悟
文选
古文选
9.11-9.13做题总结
9.11-9.13做题总结
新的日结
日常的记录
莫比乌斯反演总结
前言被各路数学题吊打之后决定苦练推式子能力。
这篇文章打算先整一点莫反的基础知识然后由易到难开始上题和写题解。
大概就是这样。
这里推荐 An_Account — 莫比乌斯反演-让我们从基础开始 ，其中的例题和本文例题有重复，本文的优势在于例题更多，难度更大以及给出了原题链接。
基本知识莫比乌斯反演 ( $M\ddot{o}bius\;Inversion$ ) 。
OI中数学题的常考知识点。
墙裂推荐 ： WeLikeStudying 的博客
莫比乌斯函数显然写过总结 ： 数论函数总结
狄利克雷卷积狄利克雷卷积 ( $Dirichlet\;convolution$ )
推荐文章（参考文章）: 算法学习笔记(35): 狄利克雷卷积，文章中给出了一些常用卷积的证明
再放一篇找到的文章留着看 ： 浅析狄利克雷卷积
以及自己之前写的一部分理论知识（已经直接copy过来了数论算法、定理和常用变换
定义 ：对于两个数论函数 $f(x),g(x)$ ，定义他们的卷积为
(f*g)(n) = \sum_{d \mid n} f(d) \cdot g(\frac{n}{d})性质：
交换律: $ ...
9.5-9.9做题总结
9.5-9.9做题总结
8.31-9.3做题总结
8.31-9.3做题总结
多项式学习笔记
做多项式题就像嗑药，出多项式题就像贩毒。——FJOI某知名选手
（这也是我选择这张头图的一个原因）
参考资料 ：
mertrshower_y’s blog
快速傅里叶变换(Fast Fourier Transform)
快速傅里叶变换，指利用计算机高效地计算离散傅里叶变换的方法，简称FFT。
离散傅里叶变换(Discrete Fourier Transform)这是一种时间复杂度为 $O(n \log n)$ 的多项式系数表示法转点值表示法的方法，简称 $DFT$。
我们有这个多项式 ：
A(x) = a_0 + a_1x + a_2x^2 + a_3x^3 + \cdots +a_nx^n然后我们按照奇偶性质，以上边那个多项式为原型得到一下两个多项式 ：
A_1(x) = a_0 + a_2x + a_4x^2 + \cdots + a_nx^{ \frac{n}{2}}
A_2(x) = a_1 + a_3x + a_5x^2 + \cdots + a_n-1x^{\frac{n}{2}-1}于是我们显然可以使用 $A_1$ 和 $A_2$ 来表示 $A$ ： ...
动态树学习笔记
本文将介绍用来解决 动态树问题 的几种数据结构。
参考资料 ： laffey’s blog
LCTLCT,即Link Cut Tree，是一种用来解决 动态树问题 的数据结构。
LCT可以依靠splay实现，也可以依靠非旋Treap实现，我曾经写了 平衡树学习笔记 来作为这篇文章的前置。
由于依靠splay实现的LCT似乎更好一些，这一部分将主要描述这种LCT。
我们以 P3690 【模板】动态树（Link Cut Tree） 为例，简要阐述这种功能强大的数据结构。
题意简述 ：
给定一颗树，支持修改点权，连边和删边，询问路径异或和。
LCT 的精髓在于 虚实链剖分 。其中虚边的链接中认父不认子，实边构成的树会形成一棵 splay 。
基本操作get 返回当前节点是父节点的左儿子还是右儿子1bool get(int x) {return rs(fa[x]) == x;}
isroot 返回当前节点是否是其所在splay的根节点1bool isroot(int x) {return ls(fa[x]) != x && rs(fa[x]) ...
平衡树学习笔记
因为考试考了LCT发现不会写所以干脆从平衡树开始复盘数据结构祭参考资料 ：自为风月马前卒的博客oi-wiki(mirror)LordLaffey’s Code
目标实现一种数据结构，维护以下功能 ：
插入数 $x$
删除一个数 $x$
查询数 $x$ 的排名
查询排名为 $x$ 的数
求 $x$ 的前驱
求 $x$ 的后继
其实就是模板题P3369
使用pb_ds实现gnu送的平衡树，可以这样用 ：
123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869#include<bits/stdc++.h>#include<ext/pb_ds/tree_policy.hpp>#include<ext/pb_ds/assoc_container.hpp>namespace Pozhu{using namespac ...