Educational Codeforces Round 133 F – Bags with Balls
题目中存在高次项的和。则我们分别计算有 $p=1,2,\cdots,n$ 个袋子选择奇数号球时的方案。对于选择了奇数号球的袋子，每个有 $\lceil \frac{m}{2} \rceil$ 种选择；偶数的则有 $\lfloor \frac{m}{2} \rfloor$ 种。因此答案为：
$$
\sum_{p=0}^{n}p^k\dbinom{n}{p}\Big\lceil\frac{m}{2}\Big\rceil^p\Big\lfloor \frac{m}{2} \Big\rfloor^{n-p}
$$
由于 $n\leq 10^9$，这式子看起来非常棘手。但我们注意到，有 $k\leq 2000$，这提示我们或许应该转变对答案的贡献方式：从高次幂入手，找到 $\mathrm{O}(\operatorname{poly} k)$ 而非 $\mathrm{O}(n)$ 的算法。 （更多…）
CodeForces Round #502 Problem G – The Tree
这是lty数据结构专题里唯二自己做出来的题目中的一道。
如果不包含“将 $x$ 的子树全部染白”的操作，应当怎样处理？
题目所给操作可以这样转述：令 $x$ 为本次染色操作的节点。若 $x$ 为白色，则立刻染黑并退出；否则我们找到其子树中的，与 $x$ 相连的黑色连通块，则对于每个连通块底部节点，若其不是叶子节点，我们将其儿子染黑。
由于本题的树没有特殊性质，且将来加入回退操作，故而难以维护整个连通块以及其叶子节点。因此，我们可以从“在何种情况下，节点 $x$ 被染黑”的方向考虑。
显然，只有从在 $x$ 到根的路径上的节点开始的染色操作，才可能波及到 $x$。假如最终 $x$ 被染黑的一瞬，它被包含在了以 $\text{comprt}$ 为根的连通块中。令链 $\langle\text{comprt}, x\rangle$ 为 $\left\{x_1,x_2,\dots,x_n \right\},x_1=\text{comprt},x_n=x$，那么自然想到，一种一定合法的染色序列是 $\{y_1,y_2,\cdots,y_n\}$，其中有 $\forall k \in [1, n] \cap \mathbb{Z},y_k \in \{x_1,\cdots,x_k\}$，也即我们每一步都在该连通块内部，并将连通块的最大深度推进一层。
这种序列确实合法（它是充分条件），但这真的是 $x$ 被染黑的必要条件么？ （更多…）
本题考查对后缀数组或后缀自动机诸多性质综合、全面的应用，以及利用可持久化数据结构查询历史区间极值的方法。
也就是说，大体思路只花费一小时不到，去掉一个 $\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)$。
有函数 $f,g$，则 $\forall n \in \mathbb{N},$
$$\begin{aligned}
f(n)=\sum\limits_{x=0}^{n}\dbinom{n}{x}g(x) &\iff g(n)=\sum\limits_{x=0}^{n}(-1)^{n-x}\dbinom{n}{x}f(x) && (1)\\
f(n)=\sum_{x=0}^{n}(-1)^x\dbinom{n}{x}g(x) &\iff g(n)=\sum\limits_{x=0}^{n}(-1)^x\dbinom{n}{x}f(x) && (2)\\
f(n)=\sum_{x=n}^{+\infty}\dbinom{x}{n}g(x) &\iff g(n)=\sum_{x=n}^{+\infty}(-1)^{x-n}\dbinom{x}{n}f(x) && (3)
\end{aligned}$$
（6月22日追记：式 $(1),(3)$ 在OI中是最常用的。尤其是 $(3)$，阐述了在计数类问题中钦定 $x$ 个元素满足某种属性（$f(x)$），其他元素任意，与恰好有 $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$。