§ 1 前言对于离散卷积式 \begin{align} c_n=\sum\limits_{i+j=n}a_ib_j \end{align}我们可以直接使用 $\rm FFT$ 求解。 考虑该问题的扩展，如何求解将 $i+j=n$ 限制中的 $+$ 换成其他运算符的卷积式。 对于 $c_n=\sum\ ...

§ 1 多项式基本操作 多项式乘法 多项式求逆 多项式除法/取模 多项式开根 多项式 $\ln$ 多项式 $\exp$ 多项式 $k$ 次幂 为简化运算，所有操作均在 ${\rm mod}\ 998244353$ 意义下进行。实现时注意清空高次系数。 代码中出现的常量、变量及函数定义如下： 123 ...

§ 1 例题一=> luogu 4721 【模板】分治 FFT§ 1.1 题意给定长度为 $n-1$ 的数组 $g[1],\ g[2],\cdots,g[n-1]$，求 $f[0],\ f[1],\cdots,\ f[n-1]$，其中 \begin{align} f[i]=\sum\limi ...

§ 1 前言本文大量参考 txc 巨爷的《基于变换合并的树上动态DP的链分治算法和全局平衡二叉树学习笔记》一文。在某些问题中，我们需要实现对某种 DP 的权值修改，以及快速询问全局或子结构的 DP 值。 如果我们能找到一种满足结合律的运算来描述转移过程的话，就可以用数据结构维护合并，降低复杂度。 ...

1. エルの楽园(→side: E→)私watashiはha…生涯shougai彼女kanojoをwo愛aiすsuるruこkoとtoはhaなnaいiだdaろroうuしshiかkaしshi…彼女kanojoとtoいiうu存在sonzaiはha…私watashiにniとtoってtte ...

§ 1 题意给定一棵有 $n$ 个节点二叉树的第 $i$ 个节点的权值 $a_i$ 以及左右儿子编号（若不存在则为 $0$）。 给出 $m$ 次操作，每次操作均为以下 $3$ 种之一： $1\ u\ v$：将节点 $u$ 的权值修改为 $v$。 $2\ u$：将节点 $u$ 及其子树内所有点的左 ...

§ 1 题意给出一个长度为 $n$ 的 $01$ 序列以及一个正整数 $k$，有 $m$ 次询问，每次给出一个区间 $[l,r]$，你可以进行若干次操作，每次选择 $[l,r]$ 的一个长度为 $k$ 的子区间，将子区间上的所有元素取反，询问至少需要多少次操作才能将 $[l,r]$ 内所有元素变成 ...

§ 1 题意对于集合 $S$，定义 $P(S)=\prod\limits_{x\in S}x$，即 $S$ 中元素之积。特别地，定义 $P(\emptyset)=1$。 记 $[n]=\lbrace 1,2,3,\cdots,n \rbrace$，对于 $n \in \mathbb{Z},\ 0\ ...

§ 1 题意记 $[n]=\lbrace 1,2,3,\cdots,n \rbrace$，对于集合 $S$ 定义 $\min S=\min\limits_{x\in S}x,\ \ F(S)=T^{\min S}$。 给出 $n,\ m,\ T$，求 $E(F(S)\ |\ S\subseteq ...

§ 1 题意给出三棵节点分别为 $n1,\ n2,\ n3$ 的树，再连两条边可构成一棵新树。 求可能形成的新树中，所有点对距离和的最大值。 $n1,\ n2,\ n3\leq 100000$。 § 2 分析对于其中一棵大小为 $n$ 的树，令 $dis_i$ 表示点 $i$ 到其他所有点的距离 ...