算法

该文为（金策《生成函数的运算与组合计数问题》）学习笔记 幂级数级数：一个有穷或无穷序列 $a_0, a_1, a_2, …$ 的形式和「即 $\sum\limits_{i = 0} a_i$」被称为级数，序列中的项称作级数的通项 敛散性：极限是无穷即为发散「如 $f(x) = x$」；极限不为无穷即为收敛「如 $f(x) = \frac{1}{x}$」 那么幂级数即为形如 $\sum\limits_{n = 0}^{\infty} a_n(x - c)^n$ 或者化简为 $\sum\limits_{n = 0}^{\infty} a_nx^n$ 的形式 形式幂级数形式幂级数$$A(x) = \sum\limits_{n = 0}^{\infty} a_nx^n$$形式与幂级数很像，但这里 $x$ 作为一个符号而不用具体数值带进去算，也不研究敛散性什么的 形式幂级数的加减乘法与多项式的有着类似的定义 实际运算时一般在 $\bmod{x^n}$ 的意义下进行，即仅取次数不超过 $n - 1$ 的项 笛卡儿积「直积」有集合 $A, B$，则 $A, B$ 的笛卡儿积记作 $A \times ...

概念引入数论函数　　　　指定义域为正整数的函数　　　　定义其加法为逐项相加，即$(f + g)(n) = f(n) + g(n)$　　　　定义其数乘为逐项相乘，即$(xf)(n) = x × f(n)$ 单位元　　　　单位元是集合中一种特别的元素，当单位元与其它元素相结合时，不会改变其它元素的值 逆元　　　　逆元是指可以取消另一给定元素运算的元素，即将其变回单位元 符号表示　　　　$[A]$表示条件$A$是否为真　　　　此处的符号”$*$”表示狄利克雷卷积 狄利克雷卷积　　令$t(n) = f(n) * g(n)$，则 　　 $$t(n) = \sum\limits_{i | n} f(i)g(\frac{n}{i})$$ 　　那么狄利克雷卷积显然有下面几个性质： 满足乘法交换律、结合律、分配律 对于单位元$\epsilon(n) = [n = 1]$，满足$\epsilon(n)*f(n) = f(n)$　　　　- 对于每一个$f(1) \ne 1$的数论函数$f(n)$，皆存在其逆元$f^{- 1}(n)$，满足$f(n) * f^{- 1}(n) = \epsilon(n)$，那 ...

树上莫队首先有一道题 王室联邦题目大意给定一棵树，将树分为大小范围为 $[B, 3B]$ 的连通块集，求方案 树上分块方法之一类似贪心，用栈维护还没有在连通块中的子节点，对于递归到的当前的点 $p$ ，扫描它的子树，能拼凑就拼凑 但是注意最后可能还会有一些点（一定包括根）剩下，那么将这些点并到最后一个连通块即可 显然每个连通块都满足大小为 $[B, 3B]$ 核心代码123456789101112131415void DFS (int root, int father) { int bot = top; for (int i = Head[root]; i; i = Link[i].next) { int v = Link[i].to; if (v == father) continue; DFS (v, root); if (top - bot >= B) { capt[++ bind] = root; while ...

前置相关 类型积性函数（注：以下皆为完全积性函数，即无需满足 $x \perp y$ 即有 $f(x) · f(y) = f(xy)$ $\epsilon (n) = [n = 1]$ $id (n) = n$ 狄利克雷卷积与莫比乌斯函数 狄利克雷卷积与欧拉函数 此处若以 $id $ 作单位元，则 $1$ 为 $\phi$ 的逆，即 $\phi * 1 = id$ 证明：由 $\sum\limits_{d | n} \phi (d) = n$ ，再带回原式可证 莫比乌斯函数与欧拉函数的转化$$\begin{aligned} \phi * 1 &= id \ \phi * 1 * \mu &= id * \mu \ \phi * \epsilon &= id * \mu \ \phi &= \sum\limits_{d | n} \mu(d) \frac{n}{d} \ \frac{\phi}{n} &= \sum\limits_{d | n} \frac{\mu(d)}{d} \end{aligned}$$ 杜教筛 杜教筛用于求解积性函 ...

处理问题$$C_i = \sum\limits_{i \oplus j} A_iB_j$$ 离散沃尔什变换「DWT」设 $DWT_i (A) = \sum\limits_{j = 0}^n A_jf(i, j)$ （第一次知道原来离散变换是这么设的） 又由于$$\begin{aligned}DWT_i(A)DWT_i(B) &= DWT_i(C) \\\sum\limits_{j = 0}^{n - 1} \sum\limits_{k = 0}^{n - 1} A_jB_kf(i, j)f(i, k) &= \sum\limits_{j = 0}^{n - 1} \sum\limits_{k = 0}^{n - 1} A_jB_kf(i, j \oplus k)\end{aligned}$$故 $f(i, j)f(i, k) = f(i, j \oplus k)​$ 于是就有一些结论 $and: f(i, j) = [(i and j) = i]$ $or: f(i, j) = [(i and j) = j]$ $xor: f(i, j) = (- ...

首先定义多项式的度数 $degA$ 为多项式 $A(x)$ 的最高次数 那么多项式 $A(x)$ 的逆即为存在多项式 $B(x)$ 使得条件满足：$$A(x)B(x) \equiv 1 \pmod{x^n}$$ 求解过程分治 $FFT$对 $A(x) = \sum\limits_{k = 0}^{n - 1} a_kx^k, B(x) = \sum\limits_{k = 0}^{n - 1} b_kx^k$ 从常数项考虑，有 $b_0 = \frac1{a_0}$，则由 $\sum\limits_{k = 0}^n b_ka_{n - k} = 0$ 可得$$b_k = \sum\limits_{i = 0}^{k - 1} b_i\left(- \frac{a_{k - i}}{a_0}\right)$$ 倍增迭代假设存在多项式 $A(x)$ ，以及其逆 $B(x)$ 满足条件 ，那么必定有$A(x)B(x) \equiv 1 \pmod{x^{\left\lceil\frac{n}{2}\right\rceil}} … (1)$ ，因为 $x^n$ 是 $x^{\left\l ...

概念引入阶对于$p \in N_+$且$(a, p) = 1$，满足$a^r \equiv 1 (mod p)$的最小的非负$r$为$a$模$p$意义下的阶，记作$\delta_p(a)$ 原根定义：若$p \in N_+$且$a \in N$，若$\delta_p(a) = \phi(p)$，则称$a$为模$p$的一个原根相关定理： 若一个数$m$拥有原根，那么它必定为$2, 4, p^t, 2p^t (p$为奇质数$)$的其中一个 每个数$p$都有$\phi(\phi(p))$个原根 　　证明：若$p \in N_+$且$(a, p) = 1$，正整数$r$满足$a^r \equiv 1 (mod p)$，那么$\delta(p) | r$，由此推广，可知$\delta(p) | \phi(p)$，所以$p$的原根个数即为$p$之前与$\phi(p)$互质的数，即$\phi(p)$故定理成立 　　　　　　- 若$g$是$m$的一个原根，则$g, g^1, g^2, …, g^{\phi(m)} (mod p)$两两不同 　　　　原根求法： ...

概念引入　　- 点值表示　　　　对于一个$n - 1$次多项式$A(x)$，可以通过确定$n$个点与值（即$x$和$y$）来表示这唯一的$A(x)$ 　　- 复数　　　　对于一元二次方程　　　　$$x^2 + 1 = 0$$　　　　在实数范围内无解，那么我们将实数范围扩充，就得到了复数，再令$i$为该方程的解，即　　　　$$i^2 = - 1$$　　　　那么就定义$z = a + bi$的数为复数，则有　　　　当$b = 0$时，$z$为实数　　　　当$b \neq 0$时，$z$为虚数　　　　当$a = 0 \&\& b \neq 0$时，$z$为纯虚数　　　　其中，复数满足加法交换律、结合律、乘法分配率等 　　　　复数相乘：$z_1 = a_1 + b_1i, z_2 = a_2 + b_2i$，则$z_1 × z_2 = (a_1 + b_1i)(a_2 + b_2i) = (a_1a_2 - b_1b_2) + (a_1b_2 + b_1a_2)i$，它们相乘还是一个复数，在复平面上理解，就是模长相乘，幅角相加 　　　　共轭复数：当两个复数实部相同，虚部为 ...