Score

100+0+0100 + 0 + 0

rk 20

Process

今天状态不好,早上眼睛好痛,9:30才开始想题。T1如此不常规的操作一看就是分块了,于是一上午都在rush T1。12:00才写完,调十分钟就过了

Summary

  • 维护奇奇怪怪的数据结构的话,一定要想分块

Problem

有向无环图 (dag)

注意到查询tt时刻xx点的值有影响的修改,实际上只有在 <t< t 的时间内,最晚一次对 xx 祖先的一操作;以及在这次操作后,所有对 xx 祖先的二操作

那么只需要找到最晚一次一操作的时间 pp ,再查询 [p,t][p, t] 时间内所有对 xx 祖先的二操作的权值最小值

维护的东西很奇怪,考虑分块

整块的信息是很好处理的,预处理 f(k,x)f(k, x) 表示第 kk 块中,最晚一次影响 xx 的一操作; g(k,x)g(k, x) 表示第 kk 块中,权值最小的影响 xx 的二操作的权值。这两个数组都可以topsort一遍扫出来

对于散块的暴力,我们需要知道当前块中的任意一点,与另外任意一点是否存在祖孙关系。如果一开始就用bitset预处理传递闭包,空间会是O(n2ω)O(\frac{n^2}{\omega})的,开不下。这里的空间优化很简单:把bitset的第二维开到块大小,处理到当前块的时候,只处理第二维是块内被询问到的点即可,空间可以重复利用。这样做一次是O(nnω)O(\frac{n\sqrt n}{\omega}),总共做n\sqrt n次,时间复杂度没有变化

总复杂度 O(nn+n2ω)O(n \sqrt n + \frac{n^2}{\omega})

code

序列 (sequence)

需要注意到一个性质,在已知 AiA_i,且确定了 Ai or Bi=xA_i \text{ or } B_i = xAi and Bi=yA_i \text{ and } B_i = y (要保证这两个值合法,即x and Ai=Aix \text{ and } A_i = A_i, y or Ai=yy \text{ or } A_i = y)后,BiB_i 是唯一确定的。这个证明很显然,列举一下m=1m = 1时的所有情况就能发现了

问题转化为,求两个序列,分别要求单调不降和单调不升且都必须合法,把方案数乘起来即为答案

以单调不降为例。对于最高位,会有一个01分界线,把数字分为两部分,左边为0右边为1,再考虑次高位,递归分成两个同样的子问题

于是区间DP,设 f(d,i,j)f(d, i, j) 表示考虑到第 dd 位,当前考虑到的区间为 [i,j][i, j] 的方案数。枚举分界位置 kk ,即 [i,k][i, k] 内的数第 dd 位为00[k+1,j][k + 1, j] 内的数第 dd 位为1。

那么 f(d,i,j)f(d1,i,k)×f(d1,k+1,j)f(d, i, j) \leftarrow f(d - 1, i, k) \times f(d - 1, k + 1, j)

同时要保证转移合法,即 [k+1,j][k + 1, j] 内的数的第 dd 位必须为1。该限制用前缀和预处理即可

总复杂度 O(mn3)O(mn^3)

code

回文串 (string)

下面用mm表示字符集大小

定义弱双回文串为,它能拆分成一个可以为空的回文串和一个非空回文串。(原题中定义的双回文串必须两个都非空)

考虑一个naive的计数方法,枚举断点位置分成两个回文串,即:

g(n)={n×mn+12n is oddn2×(mn2+mn2+1)n is even g(n) = \begin{cases} n \times m^{\frac{n + 1}{2}} &\text{n is odd}\\\\ \frac{n}{2} \times (m^{\frac{n}{2}} + m^{\frac{n}{2} + 1}) &\text{n is even} \end{cases}

显然这样会算重: 例如某个串可以被表示成 STSTSTSTSTSTSTST 的形式 (SSTT 表示两个回文串, 且 ST|ST| 是该串的最小整周期),则它会被算4次

SS + TSTSTSTTSTSTST, STSSTS + TSTSTTSTST, STSTSSTSTS + TSTTST, STSTSTSSTSTSTS + TT

那么 g(n)g(n) 本质上求的就是: 长度为 nn 的所有弱回文串的拆分方案之和

考虑枚举上述例子中的 STST,引入 f(n)f(n) 表示长度为 nn 且最小整周期也为 nn 的弱回文串数目,则 g(n)=dnf(d)nd\displaystyle g(n) = \sum_{d | n}f(d) \frac{n}{d}

h(n)h(n) 表示长度为 nn 的弱回文串数目,那么也可以得到 ffhh 的关系: h(n)=dnf(d)\displaystyle h(n) = \sum_{d | n} f(d)

于是我们就利用 ff 作为桥梁,建立起了 gghh 的关系

利用莫比乌斯反演可以得到,f=g(μ×Id)\displaystyle f = g * (\mu \times \mathrm{Id})

这一步的推导需要一个数论函数的结论: (μ×Id)Id=ϵ(\mu \times \mathrm{Id}) * \mathrm{Id} = \epsilon,这是因为 dnμ(d)d(nd)=[n=1]\displaystyle \sum_{d|n} \mu(d)d(\frac{n}{d}) = [n = 1]

于是有 h=g(μ×Id)1h = g * (\mu \times \mathrm{Id}) * 1

显然,hφ=gh * \varphi = g,而φ\varphigg的前缀和很好求,于是可以杜教筛求出hh的前缀和。

这样就能快速算出长度不超过 nn 的弱双回文串的数目,但还要减去是若双回文串,但不是双回文串的串数目。注意到这样的串即为最小整周期恰为长度本身的回文串,用上述类似方法求即可 (此时 hh 很好求,利用 hhff 的关系即可求出 ff)

时间复杂度 O(n23)O(n^{\frac{2}{3}})

code

Summary

这道题又让我进一步加深了对容斥的认识