OI

众所周知，由于做快速傅里叶变换时，要先将两个多项式 $f(x),g(x)$ 分别DFT，点值相乘后再IDFT，其常数是巨大的。但如果其系数均为实数，我们就可以通过构造多项式的方式，充分利用复数虚部存储需要的信息。下文中默认有 $\operatorname{deg}(f(x))=\operatorname{deg}(g(x))=n=2^s$。记 $n$ 次单位根为 $\omega_{n}$。

考虑构造两多项式 $p(x)=f(x)+\mathrm{i}g(x),q(x)=f(x)-\mathrm{i}g(x)$，则假若我们求出 $p(x)$ 的点值表示，就会有 $\overline{p(\omega_n^k)}=q(\omega_n^{-k\space\bmod n})$。 （更多…）

牛顿迭代法

牛顿迭代法使用泰勒级数的前若干项求出函数零点的近似解。

令 $x_0$ 为我们选定的一个接近函数 $f(x)$ 零点的横坐标。则我们进行若干次迭代。有 $$x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}$$

若 $x_0$ 选择得足够接近根 $\alpha$，迭代若干次就可以得到近似解。实际上，每进行一次迭代，解的精度变为原来的 $2$ 倍。

在多项式域上函数的推广

多项式域

（更多…）

一道让我做得相当高兴的题目。

原题链接 （这是付费比赛。）

题意简述

给定长度为 $n$ 的序列 $a$。定义函数 $f(S)=\sum\limits_{T\subseteq S} F^2(\sum_{s\in T} s)$，也即“对于 $S$ 的所有子集，求 $F(\text{子集所有元素之和})\text{的平方}$ 之和”。其中 $F(x)$ 为斐波那契数列的第 $x$ 项。有$F(0)=0, F(1)=1, F(x)=F(x-1)+F(x-2) (x > 1)$。

你需要支持以下操作，操作总数为 $m$：

1 x y：将 $a_x$ 修改为 $y$；

2 l r：输出 $\sum\limits_{i=l}^{r}\sum\limits_{j=i}^{r}f(\{a_i, a_{i+1}, \cdots, a_{j}\})$，对 $998244353$ 取模。

数据范围：对于 $\text{50\%}$ 的数据，有 $n,m\leq 100$；对于 $\text{70\%}$ 的数据，有 $n,m\leq 1000$；对于 $\text{100\%}$ 的数据，有 $n,m\leq 10^5, a_i \leq 10^5$。

（更多…）

格雷码（Gray code）是一种任意两相邻项有且仅有一位不同的二进制编码。

直观来看，其构造方式如下：假如我们构造出了格雷码$g_{0, 1, \cdots, 2^m-1}$，现在考虑构造$m+1$位格雷码。我们将前$2^m$位复制一遍，然后反转在原序列中的位置，也即$g’_{2^m+i}=g_{2^m-1-i}, i \in [0, 2^m)$；然后在最后$2^m$项格雷码的左侧分别添上$1$。由此有$g_{2^m+i}=g_{2^m-1-i}+2^m$。

实际操作时，可以采用相邻两项的异或值与前缀异或和快速构造。假若有$g_x$与$g_{x-1}$的异或值序列$s_{1, 2, \cdots, 2^m-1}$，那么便有$s_{2^m+i}=s_{i}, i \in [1, 2^m)$，同时有$s_{2^m+1}=g_{2^m+1} \oplus g_{2^m}=2^m$。

例如，前8项格雷码的二进制表示为：$\{\text{0b}000, \text{0b}00{\color{blue}1}, \text{0b}0{\color{blue}1}1, \text{0b}01{\color{blue}0}, \text{0b}{\color{blue}1}10, \text{0b}11{\color{blue}1}, \text{0b}1{\color{blue}0}1, \text{0b}10{\color{blue}0}\}$，相邻两项异或值为$\{1,2,1,4,1,2,1\}$。

（更多…）

Algorithm 457: Finding All Cliques of an Undirected Graph [H] – Coen Bron* and Joep Kerboscht – Archives of Communication of ACM

原Essay详细而准确地描述了该算法的过程，不需要额外的注解也能轻松理解。若英语阅读吃力，也有一份不错的中文详述：

极大团(maximal clique)算法:Bron-Kerbosch算法 – Bowiee – 简书

下面给出一份参考实现，能够找出所有极大团。使用unsigned long long存储各状态点的集合，二进制表示下从低到高第$(x-1)$位为$1$表示点$x$存在于集合中。 （更多…）