算法

本文将简单推导两种方式进行的离散傅里叶变换,用另种视角解释并优化算法。参考了 Seniorious yhx-12243 的 NTT 到底写了些什么(详细揭秘) 一文、OI Wiki 快速傅里叶变换 条目 和 rushcheyo 转置原理及其应用 讲稿。

离散傅里叶变换

我们计算数列 {an}\{a_n\} 的离散傅里叶变换 DFT(a,n)k=j=0n1aje2πinkj \newcommand\DFT{\operatorname{DFT}}\DFT(a,n)_k=\sum_{j=0}^{n-1}a_j\mathrm{e}^{\frac{-2\pi\mathrm{i}}{n}kj}

卷积定理循环卷积得到,我们对同样长为 nn 的数列 {bn}\{b_n\}DFT\DFT,并令数列 ck=DFT(a,n)kDFT(b,n)kc_k=\DFT(a,n)_k\DFT(b,n)_k,则有 IDFT(c,n)k=j+qk(modn)ajbq \newcommand\IDFT{\operatorname{IDFT}}\IDFT(c,n)_k=\sum_{j+q\equiv k\pmod n}a_jb_q

于是我们可以利用该原理实现常规意义下的数列卷积:有长为 nn 的数列 {an}\{a_n\},长 mm 的数列 {bm}\{b_m\},则将 a,ba,b 高位补 00,分别作 n+m1n+m-1 位的 DFT\DFT,点值相乘后 IDFT\IDFT 即可得到 ck=i+jk(modn+m1)aibj=i+j=k0i<n0j<maibjc_k=\sum_{i+j\equiv k\pmod{n+m-1}}a_ib_j=\sum_{\substack{i+j=k\\0\leq i<n\\0\leq j<m}}a_ib_j

为行文方便,下文采用 DFT(a,n)k=i=0n1aiωnik\DFT(a,n)_k=\sum_{i=0}^{n-1}a_i\omega_n^{ik} 的定义,其中 ωn=exp(2πi/n)\omega_n=\exp(2\pi\mathrm{i}/n),即 nn 阶单位根。 (更多…)

More
  • 2023年2月23日

我们可以将莫队算法从一维扩展到更高维度。

考虑正在维护 kk 维结构的信息,且每一维的大小分别为 n1,n2,,nkn_1,n_2,\cdots,n_k。为了下文叙述方便,我们将维度大小序列复制一份,得到 nk+1,,n2k(ni=nik)n_{k+1},\cdots,n_{2k}\quad(n_i=n_{i-k})。我们同时维护 2k2k 个指针,第 i  (ik)i\ \ (i\leq k) 个指针维护第 ii 维左端点,第 i  (k<i2k)i\ \ (k<i\leq 2k) 个指针维护第 iki-k 维右端点。按询问处理顺序依次移动到每个询问对应的位置上。 (更多…)

More
  • 2023年1月24日

44 道题全部只会暴力。还不如直接发下来当练习做呢,省得在场上罚坐三小时浪费时间。

简略题解

A – 神灵庙

观察发现:

  • 当树的形态确定时,我们总是将权值更大的节点安插到深度更小的叶子上。可以将 aa 降序排序后逐层填写。
  • 一个节点只可能有 00 个或者 22 个儿子。如果只有 11 个儿子,显然可将该节点删除而整棵子树全部向上平移。

f(d,i,c1,c2)f(d,i,c_1,c_2) 表示“现在位于第 dd 层(此处“层”指的是节点实际深度)。已经填写好了 a1,a2,,aia_1,a_2,\cdots,a_i,且第 dd 层共 c1c_1 个空置(非叶子)节点,第 d1d-1 层有 c2c_2 个此类节点”。那么两层的每一空置节点,均会有一个第 d+1d+1 层的儿子。枚举“下一层要填写 kk 个元素”,有转移 f(d+1,i+k,c1+c2k,c1)f(d,i,c1,c2)+(j=i+1i+kaj)(d+1)f(d+1,i+k,c_1+c_2-k,c_1)\leftarrow f(d,i,c_1,c_2)+\left(\sum_{j=i+1}^{i+k}a_j\right)(d+1) (更多…)

More
  • 2022年11月18日

昨晚参与AtCoder ABC 236时认为G题似乎可做,直到看到数据范围才发现事情没有那么简单

由于最近学习离线数据结构,又见识过一道题意接近的题目,故想到整体二分,二分每一个节点第一次能恰好经过LL条边到达的时间,然后考虑DP求解。设计状态f(i,x)f(i, x)表示在该图上经过恰好ii次转移能否到达点xx。但很快发现每一次二分时均要重新在图上运行DP,时间复杂度无法承受。况且DP递推转移的次数LL高达10910^9,甚至不可能是线性的复杂度。

今天查看题解,发现有几个重要的,从未考虑过的trick:

  1. 既然要求能够经恰好LL次转移到达的最早的时间点,则我们将每条边的边权ww设为其加入图中的时间,则可以转化成恰有LL条边的最小瓶颈路
  2. 发现LL很大,所以考虑通过矩阵乘法加速递推,也即所谓倍增优化DP的一种。

(更多…)

More
  • 2022年1月24日