「NOI2019 D1T2」「LOJ 3157」「UOJ 479」机器人 题解

「NOI2019 D1T2」「LOJ 3157」「UOJ 479」机器人 题解

LOJ链接

UOJ链接

题解

Hl,r,xH_{l,r,x}为只考虑区间[l,r][l,r],所有柱子的高度都不超过xx的方案数。我们可以枚举从它出发能走遍整个区间的那个柱子mm,设计出一个暴力的DP:Hl,r,x=mHl,m1,xHm+1,r,x1H_{l,r,x}=\sum\limits_{m}H_{l,m-1,x}H_{m+1,r,x-1}。此处mm不仅要在区间的中间部分,还要满足它可以是当前这个高度。可以发现,对于任意长度的区间,可选的mm的数量都不超过33。每个柱子可以选择的高度范围将正整数分成了许多段,同一段内的高度是否能被柱子选择的情况都是相同的。我们可以猜想fl,rf_{l,r}在每个段内都是不超过rl+1r-l+1次的多项式,并且以下做法可以证明这个结论。

从小到大考虑高度的每个段。设当前段为(a,b](a,b],区间[l,r][l,r]的所有柱子高度都不超过a+x(xN)a+x(x \in \mathbb{N})的方案数为fl,r,xf_{l,r,x}。我们通过存储关于xxrl+1r-l+1次多项式来表示fl,rf_{l,r}

此时我们已经在之前的段中算好了fl,r,0f_{l,r,0}fl,r,x=fl,r,x1+mfl,m1,xfm+1,r,x1(x>0)f_{l,r,x}=f_{l,r,x-1}+\sum\limits_{m}f_{l,m-1,x}f_{m+1,r,x-1}(x > 0)。可以发现,若f(x)f(x)是一个kk次多项式,则f(x+a)f(x+a)也是kk次多项式,且i=0xf(i)\sum\limits_{i=0}^{x}f(i)k+1k+1次多项式。这样我们就能知道fl,r,xf_{l,r,x}确实是一个rl+1r-l+1次多项式。 将当前高度区间的长度代入多项式中就能得到所有柱子的高度都在当前段及以下的情况下区间[l,r][l,r]的方案数。

有用的区间是很少的,我们可以采用记忆化搜索。分析这种做法的复杂度:每次递归时可能的mm不超过33个,递归到的长度为n2k\frac{n}{2^k}的区间不超过3k3^k个。因此,若我们对长度为ll的区间花费的时间为O(l2)O(l^2),则处理每个高度段的复杂度不超过k0(n2k)23k=n2k0(34)k=O(n2)\sum\limits_{k \geq 0}(\frac{n}{2^k})^2 \cdot 3^k=n^2 \sum\limits_{k \geq 0}(\frac{3}{4})^k=O(n^2),总复杂度不超过O(n3)O(n^3),可以通过本题(也许要卡常)。

我们有充足的时间可以进行复杂度可能很高的预处理,维护多项式并在O(n2)O(n^2)的时间内支持乘法、平移、求前缀和的方法很多,比如:

  1. 维护点值
  2. 维护牛顿级数
  3. 维护系数

笔者认为前两种做法比较好写,并且采用了第二种方法。需要注意的是,在维护点值时,不能对每个区间都维护n+1n+1个点的值,而是应该维护区间长度+1+1个点的值,并在需要升高次数的时候暴力把剩下的点的值插出来。

牛顿级数

定义(nm)={nmm!m00m<0(mZ)\binom{n}{m}=\begin{cases} \frac{n^{\underline m}}{m!} && m \geq 0 \\ 0 && m < 0 \end{cases}(m \in \mathbb{Z})Δf(x)=f(x+1)f(x)\Delta f(x)=f(x+1)-f(x)。则Δ(xm)=(xm1)\Delta \binom{x}{m}=\binom{x}{m-1}

任何一个kk次多项式f(x)f(x)都可以表示为i=0kci(xi)\sum\limits_{i=0}^{k}c_i\binom{x}{i}。且Δdf(x)=i=0kci(xid)\Delta ^d f(x)=\sum\limits_{i=0}^{k} c_i \binom{x}{i-d}(其中Δd\Delta ^d表示取ddΔ\Delta)。因此,Δdf(0)=cd\Delta^d f(0)=c_d,我们可以通过这个等式来O(k2)O(k^2)计算将多项式表示成牛顿级数时的dd次系数。

我们可以将以牛顿级数的形式表示的多项式在O(n2)O(n^2)的时间内在系数表达和点值表达之间转换,将以点值表达的牛顿级数进行平移时简单的。因此,我们可以用牛顿级数来维护本题中的多项式。

AC代码

NOI的时候我写的是O(n5)O(n^5)的分段容斥DP,只得了6060分……突然发现把直接DP改成记忆化搜索就能得9595分,心态炸了。

发表评论

电子邮件地址不会被公开。 必填项已用*标注