恒等式

$$
[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)$