恒等式

\[ [d|n]=\frac{1}{d} \sum_{i=0}^{d-1} \omega_d^{i\times n} \]

其中 \(\omega_d\) 是 \(d\) 次单位根

• 当 \(d|n\)，右边和式中每一项都为 \(1\)

• 当 \(d\nmid n\)，容易得到右边为 \(0\)

Bernoulli number

描述

Maximum-minimums identity

对于一个集合 \(S\) 有

\[ \begin{align} \max(S) &= \sum_{T \subseteq S} (-1)^{|T|+1} \min(T) \\ \min(S) &= \sum_{T \subseteq S} (-1)^{|T|+1} \max(T) \end{align} \]

其中 \(\max(S)\) 表示集合 \(S\) 中的最大元素，\(\min(S)\) 表示 \(S\) 中的最小元素

证明略

在期望下也成立

\[ \begin{align} E(\max(S)) &= \sum_{T \subseteq S} (-1)^{|T|+1} E(\min(T)) \\ E(\min(S)) &= \sum_{T \subseteq S} (-1)^{|T|+1} E(\max(T)) \end{align} \]

不会证

问题

应该是个挺简单的问题

对于 \(k=0,1,\dotsc,m\) 求

\[ f_k=\sum_{i=1}^n a_i^k \]

特征多项式

设 \(A\) 为给定的 \(n\times n\) 矩阵，\(I_n\) 为 \(n\times n\) 单位矩阵，\(A\) 的特征多项式定义为

\[ p(\lambda )=\det(\lambda I_{n}-A) \]

其中 \(\det\) 表示行列式。

Cayley–Hamilton theorem

根据 凯莱–哈密顿定理，\(A\) 满足方程

\[ p(A)=0 \]

其中 \(0\) 是零矩阵。

因此我们可以利用这个 \(n\) 次的多项式 \(p(A)\) 来降低 \(A\) 的高次幂。

可能就存个板子，而且先咕了

来更了

参考 毛啸《再探快速傅里叶变换》

好久没写博客了，不过修了好多以前文章的锅。

描述

给出一张 \(n\) 个点 \(m\) 条带权边的有向图，钦定一个根 \(r\)，求以 \(r\) 为根的最小有向生成树（Minimum Directed Spanning Tree，MDST，也即最小树形图）。

有向生成树（DST）即要求边是从父亲连向儿子。

下面给出的算法可以在 \(O(n\times m)\) 的复杂度内求解，另外存在更优的算法。

问题

求以下形式表达式的值。

\[ \sum_{i=0}^n i^{k_1}\left\lfloor \frac{a\times i+b}{c} \right\rfloor ^{k_2} \]

问题

有 \(n\) 个物品，每个物品有两个属性 \(a_i\) 和 \(b_i\)，需要选出 \(k\) 个，设选出的编号集合是 \(S\)。

最大化

\[\frac{\sum_{i\in S} a_i}{\sum_{i\in S} b_i}\]

保留一定精度。

前言

大家都会啊，还是一次考试题的部分分，听 ftq 讲了

咕了几天就来学了

好像比杜教筛少很多思维难度吧

update:

好难啊，重新理解了好多次，还改了文章结构

简介

如果一个积性函数 \(f(i)\) 在 \(i\) 是质数时是一个关于 \(i\) 的低次多项式，并且在质数的幂处的能快速求，那么大概可以用Min_25筛来求

\[\sum_{i=1}^n f(i)\]

对于 \(f(1)\) 特判

时间复杂度 \(\mathcal O(\frac{n^\frac{3}{4}}{\log n})\)，空间复杂度\(\mathcal O(\sqrt{n})\)

并且同时我们可以求出每个 \(\lfloor \frac{n}{x} \rfloor\) 的 \(\sum\limits_{i=2}^{\lfloor \frac{n}{x} \rfloor}[\text{$i$ 是质数}]f(i)\)