Charles Wu的博客

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

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

题意简述

给定长度为 $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$存在于集合中。 （更多…）

以下所有操作均可以通过递归DFS每一位并作相应判断实现。但以下写法实现简洁、常数较小，不失为一种优美的技巧。

下文采用$S_i$表示第$i$个集合，$\text{msk}$表示其二进制表示。

简单集合运算

• 并：$S_1 \cup S_2 \leftarrow \text{msk}_1 \mid \text{msk}_2$
• 交：$S_1 \cap S_2 \leftarrow \text{msk}_1\space\&\space\text{msk}_2$
• 差：$S_1 \setminus S_2 \leftarrow \text{msk}_1\space\&\space(\sim\text{msk}_2)$
• （相对于该二进制数类型最大值的）补集：$\sim\text{msk}$
• 对称差集：$S_1 \Delta S_2 \leftarrow {\text{msk}_1}^{\space\land}\space \text{msk}_2$

（更多…）

介值定理

若有连续函数$f: [a, b] \mapsto \mathbb{R}$，且不失一般性地，令$a< b, f(a)< f(b)$，则对于任意实数$x\in [f(a), f(b)]$，存在$c \in (a, b), f(c)=x$。

容易由实数完备性证明。直观理解，即可以画出一段连续曲线，其两端点分别为$(a, f(a)), (b, f(b))$，而笔不离开纸面。

离散函数值上的介值定理

若存在函数$f(x) \in \mathbb{Z}, x \in \mathbb{Z}$，且满足$|f(x)-f(x+1)|\leq 1$，则对于$a<b, f(a)<f(b)$，若有整数$x \in [f(a), f(b)]$，存在一个$c \in (a, b), f(c)=x$。

证明显然。

在OI中的实际意义？

我们常遇到这样一类函数：在某些数列上进行统计，邻项函数值之间的差为$\{-1, 0, 1\}$，如括号序前缀和（$\text{‘(‘} \rightarrow +1, \text{‘)’} \rightarrow -1$），则可以通过上述性质判断某两点之间函数值是否存在。

例如CF1695C – Zero Path，本质上路径上数字和是一个满足上述条件的整数离散函数。

再例如CF1658F – Juju and Binary String，可以将题意转化为一个函数$f(x) \in [0, n], x \in [0, n] \land \exists x_p, f(x_p) >0$，且满足上述性质；同时有函数$g(x)=x, x \in [1, n]$，则可以证明一定存在$x_0, g(x_0)=f(x_0)$。

考虑合并若干重叠线段。使其有序化后考虑每两个线段的交，如果其为空则新建一条独立线段，反之合并。

最后应当恰好有$7$条水平线段，$8$条垂直线段，否则依题意不可能拼凑出“$\textbf{THUPC}$”图形。

DFS搜索组成每个字母的所有可能线段组合。需要合理剪枝，亦可以使用二进制状态压缩减小常数。时间复杂度理论上限为$\mathrm{O}(7^5\times 8^5)$，实际远远达不到。

赛时1A（实际上因为无主函数返回值RE了两次）$7\text{KB}$代码： （更多…）