There’s no feeling more intense than starting over.

If you’ve deleted your homework the day before it was due, as I have. Or if you left your wallet at home and you have to go back after spending an hour in the commute. If you won some money at the casino and then put all your winnings on red and it came up black. If you got your best shirt drycleaned before a wedding and then immediately dropped food on it. If you won an argument with a friend and then later discovered that they just returned to the original view.

Starting over is harder than starting up. If you’re not ready for that, like if you’ve already had a bad day, then what you’re about to go through might be too much. Feel free to go away and come back. I’ll be here.

(更多…)

More
  • 2022年9月11日

Educational Codeforces Round 133 F – Bags with Balls

题目中存在高次项的和。则我们分别计算有 p=1,2,,np=1,2,\cdots,n 个袋子选择奇数号球时的方案。对于选择了奇数号球的袋子,每个有 m2\lceil \frac{m}{2} \rceil 种选择;偶数的则有 m2\lfloor \frac{m}{2} \rfloor 种。因此答案为: p=0npk(np)m2pm2np \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}

由于 n109n\leq 10^9,这式子看起来非常棘手。但我们注意到,有 k2000k\leq 2000,这提示我们或许应该转变对答案的贡献方式:从高次幂入手,找到 O(polyk)\mathrm{O}(\operatorname{poly} k) 而非 O(n)\mathrm{O}(n) 的算法。 (更多…)

More
  • 2022年8月8日

CodeForces Round #502 Problem G – The Tree

这是lty数据结构专题里唯二自己做出来的题目中的一道。

如果不包含“将 xx 的子树全部染白”的操作,应当怎样处理?

题目所给操作可以这样转述:令 xx 为本次染色操作的节点。若 xx 为白色,则立刻染黑并退出;否则我们找到其子树中的,与 xx 相连的黑色连通块,则对于每个连通块底部节点,若其不是叶子节点,我们将其儿子染黑。

由于本题的树没有特殊性质,且将来加入回退操作,故而难以维护整个连通块以及其叶子节点。因此,我们可以从“在何种情况下,节点 xx 被染黑”的方向考虑。

显然,只有从在 xx 到根的路径上的节点开始的染色操作,才可能波及到 xx。假如最终 xx 被染黑的一瞬,它被包含在了以 comprt\text{comprt} 为根的连通块中。令链 comprt,x\langle\text{comprt}, x\rangle{x1,x2,,xn},x1=comprt,xn=x\left\{x_1,x_2,\dots,x_n \right\},x_1=\text{comprt},x_n=x,那么自然想到,一种一定合法的染色序列是 {y1,y2,,yn}\{y_1,y_2,\cdots,y_n\},其中有 k[1,n]Z,yk{x1,,xk}\forall k \in [1, n] \cap \mathbb{Z},y_k \in \{x_1,\cdots,x_k\},也即我们每一步都在该连通块内部,并将连通块的最大深度推进一层

这种序列确实合法(它是充分条件),但这真的是 xx 被染黑的必要条件么? (更多…)

More
  • 2022年7月16日

洛谷题库 P4770 [NOI2018] 你的名字

本题考查对后缀数组或后缀自动机诸多性质综合、全面的应用,以及利用可持久化数据结构查询历史区间极值的方法。

也就是说,大体思路只花费一小时不到,去掉一个 log\log 却耗了我一天多……

“双指针”扫描求串 TT 的每个前缀在 SS 中匹配的最长子串

在任何时刻,SAM 的状态转移函数会将某字符串引向串 SS 中的等价 endpos\mathrm{endpos} 状态。根据 endpos\mathrm{endpos} 和 parent tree 的性质,我们可以对前缀 T[1k],k{1,2,,T}T[1\cdots k], k \in \{1, 2,\cdots, |T|\} 依次求出其最长的作为 SS 的子串出现的后缀。 (更多…)

More
  • 2022年7月9日

我们实现NTT时,总是在 整数模质数 p=2kq+1p=2^kq+1 上进行的。原因很简单:为了在 Z/pZ\mathbb{Z}/p\mathbb{Z} 上使用原根以套用复数域 C\mathbb{C} 上“单位根”的概念,其阶必然也应当是 2k2^k 的倍数才行。这就为我们带来了很多不便。假如现在给定一质数 pp’ 且不保证有 p=2kq+1p’=2^kq+1,我们就需要另辟蹊径完成卷积。

实现一:中国剩余定理

中国剩余定理:若数 nn 的质因数分解为 i=1kpiei\sum_{i=1}^{k}p_i^{e_i},有整数模 nn 加法(或者,随便你怎么叫吧)

Z/nZZ/p1e1Z×Z/p2e2Z××Z/pkekZ\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}

或者通俗地讲,若 m1,m2,,mkm_1, m_2, \cdots, m_k 两两互质,则线性同余方程组 {xx1(modm1)xx2(modm2)xxk(modmk)\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.modi=1kmi\bmod \prod_{i=1}^{k}m_i 意义下有唯一解。 (更多…)

More
  • 2022年7月3日

众所周知,由于做快速傅里叶变换时,要先将两个多项式 f(x),g(x)f(x),g(x) 分别DFT,点值相乘后再IDFT,其常数是巨大的。但如果其系数均为实数,我们就可以通过构造多项式的方式,充分利用复数虚部存储需要的信息。下文中默认有 deg(f(x))=deg(g(x))=n=2s\operatorname{deg}(f(x))=\operatorname{deg}(g(x))=n=2^s。记 nn 次单位根为 ωn\omega_{n}

考虑构造两多项式 p(x)=f(x)+ig(x),q(x)=f(x)ig(x)p(x)=f(x)+\mathrm{i}g(x),q(x)=f(x)-\mathrm{i}g(x),则假若我们求出 p(x)p(x) 的点值表示,就会有 p(ωnk)=q(ωnk modn)\overline{p(\omega_n^k)}=q(\omega_n^{-k\space\bmod n})(更多…)

More
  • 2022年7月3日

洛谷题库 P4721【模板】分治FFT

给定数列 g1ng_{1\cdots n},求解满足如下形式的数列 fff0=1,fi=j=0i1fjgij,i{1,2,,n}f_0=1,f_i=\sum_{j=0}^{i-1}f_jg_{i-j},\forall i \in \{1,2,\cdots,n\},对 998244353998244353 取模。

这道题可以通过多项式求逆解决。我们在此不作讨论。

考虑其转移形式,全部都是依赖于前序已求出项的、固定系数的线性转移。则可以考虑CDQ分治。如果你愿意,也可以叫作“分治FFT”。

假设正处理区间 [l,r][l, r];令 mid=(l+r)/2\text{mid}=\lceil (l+r)/2\rceil,我们已经计算好 fl,,midf_{l,\cdots,\text{mid}}。现统一处理左半区间对右半的贡献。

则令考虑的乘积项为 fi,i[l,mid]f_i, i \in [l, \text{mid}],要向 fj,j(mid,r]f_j, j \in (\text{mid}, r] 作贡献。有 fjgjifif_j \leftarrow g_{j-i}f_i。故而对于 i[l,mid]i \in [l, \text{mid}],其将分别与 gmid+1l,,rl,gmidl,,rl1,,g1,,rmidg_{\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)F(x), G(x),有 [xi]F(x)=fi+l,[xj]G(x)=gj1[x^i]F(x)=f_{i+l}, [x^j]G(x)=g_{j-1},将其二者作卷积,他们对 fj,j(mid,r]f_j, j \in (\text{mid}, r] 的贡献即为 [xjl1]F(x)G(x)[x^{j-l-1}]F(x)G(x)

(更多…)

More
  • 2022年7月3日

牛顿迭代法

牛顿迭代法使用泰勒级数的前若干项求出函数零点的近似解。

x0x_0 为我们选定的一个接近函数 f(x)f(x) 零点的横坐标。则我们进行若干次迭代。有 xn+1=xnf(xn)f(xn) x_{n+1}=x_n-\dfrac{f(x_n)}{f'(x_n)}

x0x_0 选择得足够接近根 α\alpha,迭代若干次就可以得到近似解。实际上,每进行一次迭代,解的精度变为原来的 22 倍。

在多项式域上函数的推广

多项式域

(更多…)

More
  • 2022年6月24日

二项式反演

有函数 f,gf,g,则 nN,\forall n \in \mathbb{N}, f(n)=x=0n(nx)g(x)    g(n)=x=0n(1)nx(nx)f(x)(1)f(n)=x=0n(1)x(nx)g(x)    g(n)=x=0n(1)x(nx)f(x)(2)f(n)=x=n+(xn)g(x)    g(n)=x=n+(1)xn(xn)f(x)(3)\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)(1),(3) 在OI中是最常用的。尤其是 (3)(3),阐述了在计数类问题中钦定 xx 个元素满足某种属性(f(x)f(x)),其他元素任意,与恰好xx 个元素满足某种属性(g(x)g(x))之间的对应关系。)

证明

(更多…)

More
  • 2022年6月21日