本题考查对后缀数组或后缀自动机诸多性质综合、全面的应用，以及利用可持久化数据结构查询历史区间极值的方法。
也就是说，大体思路只花费一小时不到，去掉一个 $\log$ 却耗了我一天多……
在任何时刻，SAM 的状态转移函数会将某字符串引向串 $S$ 中的等价 $\mathrm{endpos}$ 状态。根据 $\mathrm{endpos}$ 和 parent tree 的性质，我们可以对前缀 $T[1\cdots k], k \in \{1, 2,\cdots, |T|\}$ 依次求出其最长的作为 $S$ 的子串出现的后缀。 （更多…）
我们实现NTT时，总是在 整数模质数 $p=2^kq+1$ 域上进行的。原因很简单：为了在 $\mathbb{Z}/p\mathbb{Z}$ 上使用原根以套用复数域 $\mathbb{C}$ 上“单位根”的概念，其阶必然也应当是 $2^k$ 的倍数才行。这就为我们带来了很多不便。假如现在给定一质数 $p’$ 且不保证有 $p’=2^kq+1$，我们就需要另辟蹊径完成卷积。
中国剩余定理：若数 $n$ 的质因数分解为 $\sum_{i=1}^{k}p_i^{e_i}$，有整数模 $n$ 加法群（或者环，随便你怎么叫吧）
$$\mathbb{Z}/n\mathbb{Z}\cong \mathbb{Z}/p_1^{e1}\mathbb{Z}\times \mathbb{Z}/p_2^{e2}\mathbb{Z}\times \cdots \times\mathbb{Z}/p_k^{ek}\mathbb{Z}$$
或者通俗地讲，若 $m_1, m_2, \cdots, m_k$ 两两互质，则线性同余方程组
$$\left\{\begin{aligned}
x &\equiv x_1\pmod{m_1}\\
x &\equiv x_2\pmod{m_2}\\
&\quad \vdots\\
x &\equiv x_k\pmod{m_k}\end{aligned}\right.$$
在 $\bmod \prod_{i=1}^{k}m_i$ 意义下有唯一解。 （更多…）
众所周知，由于做快速傅里叶变换时，要先将两个多项式 $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})$。 （更多…）
给定数列 $g_{1\cdots n}$，求解满足如下形式的数列 $f$：$f_0=1,f_i=\sum_{j=0}^{i-1}f_jg_{i-j},\forall i \in \{1,2,\cdots,n\}$，对 $998244353$ 取模。
这道题可以通过多项式求逆解决。我们在此不作讨论。
考虑其转移形式，全部都是依赖于前序已求出项的、固定系数的线性转移。则可以考虑CDQ分治。如果你愿意，也可以叫作“分治FFT”。
假设正处理区间 $[l, r]$；令 $\text{mid}=\lceil (l+r)/2\rceil$，我们已经计算好 $f_{l,\cdots,\text{mid}}$。现统一处理左半区间对右半的贡献。
则令考虑的乘积项为 $f_i, i \in [l, \text{mid}]$，要向 $f_j, j \in (\text{mid}, r]$ 作贡献。有 $f_j \leftarrow g_{j-i}f_i$。故而对于 $i \in [l, \text{mid}]$，其将分别与 $g_{\text{mid}+1-l, \cdots, r-l}, g_{\text{mid}-l, \cdots, r-l-1}, \cdots, g_{1, \cdots, r-\text{mid}}$ 作卷积。其二者下标的和即为贡献对象。故而我们构造两个多项式 $F(x), G(x)$，有 $[x^i]F(x)=f_{i+l}, [x^j]G(x)=g_{j-1}$，将其二者作卷积，他们对 $f_j, j \in (\text{mid}, r]$ 的贡献即为 $[x^{j-l-1}]F(x)G(x)$。
一道让我做得相当高兴的题目。
原题链接 （这是付费比赛。）
给定长度为 $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$。
通过优化，将子集求和类相关问题的时间复杂度由朴素的 $\mathrm{O}(3^n)$ 优化到 $\mathrm{O}(n\times 2^n)$。
一场相当有收获的比赛。比赛链接
尝试观察规律。我们发现，在完成$s$次操作以后，左端点的可能取值为$\dfrac{xa+(2^s-x)b}{2^s}, x \in [1, 2^s]$，右端点的可能取值为$\dfrac{xa+(2^s-x)b}{2^s}, x \in [0, 2^s)$。假如现在我们达到最终状态，其$l=\dfrac{(x+1)a+(2^s-x-1)b}{2^s}, r=\dfrac{xa+(2^s-x)b}{2^s}$。那么，在$x$的二进制表示中，如果从高到底第$\mathrm{pos}$位为$1$，则在第$\mathrm{pos}$轮中，有check (mid) == 0，向右区间递归；否则向左区间递归。这是很容易解释的：若向右递归，则右端点不变。而在下一层，右端点表示中$a, b$的所有系数乘$2$，所以体现为二进制位末尾添一个$0$。反之，就变成$(x+(x+1))/2$，在下一层中体现为$2x+1$。如果其有$\operatorname{popc}(x)$位为$1$，则到达该状态的概率为$p_0^{\operatorname{popc}(x)}p_1^{s-\operatorname{popc}(x)}$。
以$s=3$时的状态$l=\dfrac{3a+5b}{8}, r=\dfrac{2a+6b}{8}$为例。$2$的三位二进制表示为$\text{0b010}$，则推断出在前三轮分别向右、左、右区间递归，到达其的概率为$p_0p_1^2$。 （更多…）
格雷码（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\}$。
原Essay详细而准确地描述了该算法的过程，不需要额外的注解也能轻松理解。若英语阅读吃力，也有一份不错的中文详述：
下面给出一份参考实现，能够找出所有极大团。使用unsigned long long存储各状态点的集合，二进制表示下从低到高第$(x-1)$位为$1$表示点$x$存在于集合中。 （更多…）