拉格朗日插值法用来在 $O(n ^2)$ 的时间内解决已知多项式点值表达求系数表达的问题。

给定 $n$ 个点 $(x _1, y _1), \dots, (x _n, y _n)$,求出这 $n$ 个点确定的一个 $n - 1$ 次的多项式。

阅读全文 »

比较严谨的东西就略过了,这里讲的主要是做题要用到的一些技巧。

这里个人认为生成函数的卷积本质上都是枚举了划分,有标号则需要组合数来分配标号(若这些物品本质一样,需要除掉阶乘),无标号不管。

阅读全文 »

Description

给出 $n$,求
$$
\sum _{i = 0} ^n \sum _{j = 0} ^i \begin{Bmatrix} i \\ j \end{Bmatrix} j! 2 ^j
$$
其中 $\begin{Bmatrix} i \\ j \end{Bmatrix}$ 表示第二类斯特林数,也即将 $i$ 划分成 $j$ 个非空集合的方案数。
$$
1 \le n \le 10 ^5 \\
\texttt{Bonus:} n \le 10 ^7
$$

阅读全文 »

Description

$n$ 个点,每个点有点权 $a _i$,$i, j$ 之间有边当且仅当 $a _i \text{ AND } a _j = 0$。执行以下过程 $n$ 次:

  1. 选择一个点 $u$ 染色。
  2. 选择一个与 $u$ 相连的且已经染色的点 $v$,将 $a _v$ 计入答案。如果没有合法的 $v$,跳过该步。

输出最大的答案。

$$
1 \le n \le 2 \times 10 ^5, 0 \le a _i \le 2 \times 10 ^5
$$

阅读全文 »