UOJ Logo vfleaking的博客

博客

UOJ Round #3 题解

2014-12-21 22:36:52 By vfleaking

核聚变反应强度

算法一

对于 $n=1$ 的数据,就是求一个数次大的约数。

众所周知一个数$x$的约数是成对出现的($d$、$\frac{x}{d}$),其中总有一个不超过$\sqrt{x}$。所以从$1$到$\sqrt{a_1}$地枚举$d$就能找出所有$a_1$的约数了。排序输出次大的即可。

复杂度:$O(\sqrt{a})$

算法二

先找出$a_1$的所有约数,然后枚举$i$,$\text{sgcd}(a_1,a_i)$显然也是$a_1$的约数,所以枚举$a_1$的所有约数,找到是$a_i$约数的次大的即可。

复杂度:$O(n\sqrt{a})$

算法三

考虑分解质因子后:

$a=p_1^{x_1}p_2^{x_2}...p_m^{x_m}$

$b=p_1^{y_1}p_2^{y_2}...p_m^{y_m}$

则:$\gcd(a,b)=p_1^{\min(x_1,y_1)}p_2^{\min(x_2,y_2)}...p_m^{\min(x_m,y_m)}$

我们发现,$a$和$b$的公约数都一定是$\gcd(a,b)$的约数。那么为了得到次大公约数,只需求出$\gcd(a,b)$,再除去一个最小的公共质因子即可。

对$a_1$用$O(\sqrt{a_1})$的时间分解得到$O(\log(a_1))$个质因数,每次对于$a_i$,先求出$g=\gcd(a_1,a_i)$,然后枚举$a_1$的每个质因数,找到最小的能整除$g$那个,设其为$p$,$g/p$即为所求。(不存在则为输出$-1$)

复杂度:$O(\sqrt{a}+n \log(a))$

一个骗分算法

考虑算法二,我们预先对 $a_1$ 的约数们排好序,然后枚举 $i$,从约数表里每次二分到 $\gcd(a_1,a_i)$所在位置,再往前枚举,找到第一个能整除$a_i$的即为次大公约数。

虽然复杂度不靠谱,但是对于$a_i \leq 10^{12}$的范围实际运行速度十分优秀。需要构造针对的数据才能卡住。

还有另一个骗分算法,求出 $\gcd$ 然后暴力枚举最小质因子。好多人写这个啊……你们都没意识到复杂度不对么……放你们一马给了 80 分。

(有这种闲心的为啥不写正解啊,你们考虑过 maker 的感受吗!QAQ)

铀仓库

算法一

我们先来证明几个显然的结论。

结论一:小O的行动一定是,每次看准一个箱子,从$s$跑过去拿起来,然后直接搬回$s$。

首先,小O一定不会把一个箱子搬到离$s$更远的地方。其次我们考虑,如果小O进行了这样的动作:从$a$搬到$b$、从$c$搬到$d$,其中$a < b < c < d < s$,那么等价于从$a$搬到$d$,从$c$搬到$b$,显然干了多余的事。

结论二:起始位置$s$一定有箱子。

考虑确定了$s$,一定是搬来前若干近的箱子,也就一定是连续的一段,所耗时间为距离和的两倍。我们知道,给定数轴上若干个点,选一个坐标最小化每个点到它的距离和,那么一定是选这些点坐标中的中位数(调整法可证)。

说了一大堆废话,我们得到一个暴力做法。枚举$s$,每次拿来一个最近的即可。

复杂度:$O(n^2T)$

算法二

枚举$s$,由于是取前若干近的过来,我们二分取的最远的在哪。如果$x_i=i$那么直接可以$O(1)$确定左右端点,否则我们需要再一次二分确定左右端点。

复杂度:$O(n \log n \log X)$,$X$表示坐标范围。

算法三

先二分答案,于是问题变成了:求叠到$K$个箱子所需的最短时间。

由于取的一定是连续的一段,设其为$[l,r]$,若$a_i=1$,我们直接从左到右枚举$s$,此时由于左边的越来越远,右边的越来越近,$l、r$一定是非降的。所以,每次$s$右移的时候,判断$r+1$处是否比$l$近,如果是就一直替换,直到不是为止。

移动左右端点的同时顺便维护一下距离和就好了。

这样的复杂度是$O(n+Σa_i)$的,还是不能通过全部数据。

加一个小优化就好了。把每个位置的$a_i$个箱子想象成横着紧贴成一排,称为一组箱子,那么每次我们移动左右端点$l、r$的时候,事实上是干了很多重复的事情的。

如果$l$、$r$所在箱子组都不变,那么会一直进行替换,直到某个端点换组。所以在每次替换的时候,直接加速到某个端点换组的时刻即可。

复杂度:$O(n \log X)$

链式反应

算法一

按照题意进行爆搜,可以通过第一个测试点获得 10 分。

算法二

我们得思考一下这题题意到底是啥意思。其实说,一棵有标号的树,编号满足堆的性质,对于儿子方向每个结点有两条红色边,$c$ 条黄色边,$c$ 属于集合 $A$,统计方案数。

所以我们用 $f[n]$ 表示 $n$ 个结点的这个样子的树的方案数。然后要么 $1$ 号点没有进行核裂变,此时必有 $n = 1$ 且 $f[n] = 1$。要么 $1$ 号结点进行了核裂变,此时我们枚举两个中子打中的结点的子树的大小 $j, k$,剩下的就是被破坏死光打中的,于是要满足 $i - 1 - j - k \in A$。然后考虑两个中子打中的结点的子树,我们先选出它们的编号,方案数是 $\binom{i - 1}{j} \cdot \binom{i - 1 - j}{k}$,然后我们就可以安全地把这两棵子树的结点都重标号,方案数自然是 $f[j]$ 和 $f[k]$。所以我们把这些杂八事综合起来就得到了一个简单的DP:$f[i] = \sum_{j}{\sum_{k}{\binom{i - 1}{j} \cdot \binom{i - 1 - j}{k} \cdot f[j] \cdot f[k]}}$。这里的 $j, k$ 要满足 $i - 1 - j - k \in A$。直接暴力递推就得到了一个 $O(n^3)$ 的算法。

什么,过不了样例?当然过不了样例了,因为有重复计数。那两个中子是等价的,一个方案自然会被统计了两遍,只要把 DP 方程除以 $2$ 就好了。

可以通过前 $4$ 个测试点获得 40 分。

算法三

其实只要在算法二基础上优化就行了。我们仔细观察式子:$\binom{i - 1}{j} \cdot \binom{i - 1 - j}{k} = \frac{(i - 1)!}{j! k! (i - j - k - 1)!}$。有四个部分,第一个只跟 $i$ 有关,第二个只跟 $j$ 有关,第三个只跟 $k$ 有关,第四个只跟 $i - j - k - 1$ 有关。所以我们可以递推一个 $g[i] = \sum_{k}{\frac{f[k]}{k!} \frac{f[i - k]}{(i - k)!}}$。然后递推 $f[i]$ 时我们枚举 $j + k$ 的和 $s$,那么直接读取 $g[s]$ 的值,然后剩下的部分就是一些跟 $i$ 和 $s$ 有关的了。

好像说得挺意识流的,具体就是:$f[i] = \frac{1}{2}\sum_{s}{g[s] \cdot \frac{(i - 1)!}{(i - s - 1)!}}$。$s$ 要满足 $i - s - 1 \in A$。

可以通过前 $6$ 个测试点获得 60 分。

算法四

再观察一下式子,搞个数组 $a$,其中如果 $i \in A$ 则 $a_i = \frac{1}{i!}$,否则为 $0$。然后原递推式的右边的第 $i$ 项其实就是 $g$ 跟 $a$ 的卷积的第 $i - 1$ 项然后再乘以 $(i - 1)!$。然后其实 $g$ 本身也是个卷积,就是 $\frac{f[i]}{i!}$ 这个数列的平方。

我们可以使用分治。每次分治一个区间 $[l, r]$,我们找出中点 $m$,然后递归 $[l, m]$,然后求出 $[l, m]$ 对 $[m + 1, r]$ 的贡献,再递归右边。

考虑左边对右边的贡献,“$\binom{i - 1}{j} \cdot \binom{i - 1 - j}{k} \cdot f[j] \cdot f[k]$” 中,左边可能作为 $f[j]$ 也可能作为 $f[k]$ 出现,也可能都出现。我们只要考虑这几种情况然后分别进行 FFT 就行了。看起来要和整个 $a$ 或者 $f$ 进行卷积?其实不然,只用取出一个长度为分治时的区间的长度的前缀就可以了。

时间复杂度 $O(n \log^2 n)$。可以通过前 $9$ 个测试点获得 90 分。常数小的话应该能过。

算法五

以下内容需要一点微积分知识……如果是微积分恐惧症……您还是看算法四加卡常数吧~我还是很良心的没让所有人都非得用算法五才能AC~

嗯,既然都发现是卷积了,那么肯定少不了生成函数。我们记 $\frac{f[i]}{i!}$ 的生成函数为 $x(t)$,$a_i$ 的生成函数为 $a(t)$,那么生成函数就要满足:$x'(t) = \frac{1}{2}a(t)x^2(t) + 1$。

拨一下 mathematica 就会发现它解不出来这个微分方程,所以只有自力更生了。

首先科普下一般来说应该怎么解一个多项式方程(更严谨地说这里应该是形式幂级数)。假设 $x(t)$ 满足 $f(x(t)) = 0$,那么我们先求出 $0$ 次项的系数,然后每次倍增。也就是说每次我们有一个多项式 $x_n$ 满足 $x_n$ 和 $x$ 的前 $n$ 项系数是一样的,我们记为 $x \equiv x_n \pmod{t^n}$,然后我们要求出 $x_{2n}$ 满足 $x \equiv x_{2n} \pmod{t^{2n}}$。使用泰勒展开可以得到:

\begin{equation} 0 = f(x_{2n}) = f(x_n) + f'(x_{n}) (x_{2n} - x_n) + \frac{1}{2} f''(x_{n}) (x_{2n} - x_n)^2 + \dots \end{equation}

注意到如果只考虑前 $2n$ 项,那么就可以去掉二次项及之后的项然后解出:

\begin{equation} x_{2n} \equiv x_n - \frac{f(x_n)}{f'(x_n)} \pmod{t^{2n}} \end{equation}

由于 $T(n) = T(n / 2) + O(n \log n)$ 解出来是 $T(n) = O(n \log n)$,所以只要能足够快地把 $x$ 带入 $f(x)$,那么就能 $O(n \log n)$ 解方程。(当然需要 FFT 做多项式乘法)

什么这里有个除法?我们可以利用牛顿迭代求出一个形式幂级数的乘法逆元,于是就能做除法了。

于是微分方程也可以如法炮制,假设有个这样的一阶微分方程:

\begin{equation} \frac{d}{dt}x = f(x) \end{equation}

我们还是老样子:

\begin{eqnarray} \frac{d}{dt}x_{2n} & \equiv & f(x_n) + f'(x_n) \cdot (x_{2n} - x_n) \pmod{t^{2n}}\\\\ & \equiv & f(x_n) + f'(x_n) \cdot x_{2n} - f'(x_n) \cdot x_n \pmod{t^{2n}} \end{eqnarray}

所以问题变成了这玩意儿怎么解……而这玩意儿其实很好解……我们两边同时乘以 $e^{-\int{f'(x_n) dt}}$(囧……由于公式嵌套过多,排版已经开始混乱了),记作 $r$:

\begin{eqnarray} \frac{d}{dt}x_{2n}\cdot r & \equiv & (f(x_n) - f'(x_n) \cdot x_n) \cdot r + f'(x_n) \cdot x_{2n} \cdot r \pmod{t^{2n}}\\\\ \frac{d}{dt}(x_{2n}\cdot r) & \equiv & (f(x_n) - f'(x_n) \cdot x_n) \cdot r \pmod{t^{2n}} \end{eqnarray}

然后只要把右边积分再除以 $r$ 就行了。

注意到虽然人类无法方便地给任意函数积分,但是给多项式求导和求积分简直易如反掌。所以唯一的难点在于 $r$ 怎么求。

好吧其实我几个月前 YY 到这里直接就弃疗了,后来翻了翻论文,知道了怎么求 $e^x$。由于 $e^x$ 的反函数是 $\ln(x)$ 而 $\ln(x)$ 对 $t$ 的导数是 $\frac{x'}{x}$,所以 $\ln(x)$ 可以快速求,然后我们就可以进行牛顿迭代求 $\ln(x)$ 的反函数得到 $e^x$。

对于本题,$f(x) = \frac{1}{2} ax^2 + 1$,然后无脑使用上述方法就行了。

本来还想当一个原创算法呢……结果后来发现国外论文上早就有了……果然我还是太naive……

时间复杂度 $O(n \log n)$。可以通过所有测试点获得 100 分。

形式幂级数真是个优美的东西啊,很多在实数域内有条件收敛的算法,到形式幂级数上就一定收敛了,我不得不表示赞叹。

评论

delayyy
沙发
Picks
板凳
phile
前排
tm
A题好水。。。一眼题
thomount
最后一次用Pascal,竟然惨成这样。。。被语言坑啊。。。TAT
naive
怒赞~\(≧▽≦)/~
Gromah
Rating掉得真开心。
jiry_2
感觉我的OI生涯就是拿来搞笑的。。
Starzxy
远距离orz!
TKD
orz
dmcyer
好评
hzyfr
UOJ会成为FFTOJ么...3发比赛两题FFT
phoenix
orz
Prime
真棒!!
loriex
orz
hzyfr
@vfleaking 您的标程都跑了3s+,算法四多个log真的能卡进4s内么?
vfleaking
@hzyfr 这个真的可以……因为常数小……裸写的话大概是4秒多一点,然后分治时注意到有很多次dft是对着同一个数组的……优化下…… 然后还可以利用fft是循环卷积的性质……所以你可以把“dft两次再idft”的模式扔进垃圾桶……预先开个比较大的数组,然后狂dft呀乘起来什么的,到最后再idft,中间任由它爆(因为反正最后我们只需要知道乘积的后半段……)
hzyfr
有一个地方看不懂,就是求多项式,为什么会涉及到$e^x$,然后这东西又怎么变成多项式?
vfleaking
@hzyfr 其实他们是形式幂级数。你可以粗略地感受一下,$f(z)$ 和 $g(z)$ 加减乘除还是形式幂级数(除法时0是个例外 = =……)。。他们还能求导求积分。。 这意味着可以像实数差不多的样子用……(说白了就是形式幂级数带上加和乘形成了一个域,且能在上面定义导数什么的……) 所以微积分的相关玩法还是成立的。 随便给个不奇葩的函数展开成形式幂级数的方法差不多就是泰勒展开就行了。比如 $e^z = \sum_{k \geq 0}{\frac{z^k}{k!}}$…… 然后随便给两个 $f$ 和 $g$,我们可以把他们套起来 $f(g(z))$。 所以 $e^{f(z)}$ 的意思就很明显了。
thomount
@vfleaking 上述题解中间,提及“两边同时乘以 e−∫f′(xn)dte−∫f′(xn)dt”,请问为什么要乘这个? 下面式子中怎样消去的最后一项?

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。