nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
分块已知某函数$f(x)$对于$x\in[l,r]$，有$f(x)$关于$x$单调，且$f(x)$值域远小于$x$的定义域。
现在要你求$\sum_{x=1}^n g(x,f(x))$
那么我们就可以根据$f(x)$对$g$进行分块，在这一块中，始终有常数$y=f(x)$，然后对$h(x)=g(x,y)$统计$x$的前缀和。
最终我们就能很快的计算答案。
阅读全文
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
前言关于生成函数有很多概念模糊的地方，比如生成函数的乘法是怎么定义的，比如乘法可以换序吗？比如为什么可以把多项式变成对数函数？为什么又可以使用泰勒展开？
前置知识代数系统，群论
环环是一个具有两个二元运算的代数系统。环$\lt R,+,\circ\gt$满足
$\lt R,+\gt$构成交换群， 即$+$满足封闭性、结合律、单位元、逆元、交换律
$\lt R,\circ\gt$构成半群， 即$\cdot$满足封闭性、结合律、单位元
$\circ$对$+$有分配率，即$a\circ(b+c)=a\circ b+a\circ c$
阅读全文
nexthexonextbutterflyvolantisyearnyiliashokaindigoapollolandscapecactusmateryicarusfluidmaterial
集合论集合论是群论的基础，群论是建立在集合论上的。
集合的基本操作集合的交$$A \cap B = \lbrace x \vert x \in A \wedge x \in B \rbrace$$
集合的并$$A \cup B = \lbrace x\vert x \in A \vee x \in B \rbrace$$
集合的笛卡尔积注意到笛卡尔积是一个二元组。$$A \times B = \lbrace (x,y) \vert x \in A \wedge y \in B \rbrace$$
集合的映射我们定义一个映射$f$满足 $f(x) = y $， 其中 $x\in A$， $y\in B$， 即映射可以把一个集合A中的元素映射到集合B中的一个元素。
可以称映射$f$作用于集合A，映射到集合B
阅读全文