【题解】[NOI Online #3 提高组] 优秀子序列

[NOI Online #3 提高组] 优秀子序列

给定长度为 $n$ 的非负整数序列 $\{a_n\}$,定义一个子序列 $\{b_i\}$ 是优秀的,当且仅当:$b_i<b_{i+1},\forall i\ne j\ a_{b_i}\text{and} a_{b_j}=0$。
一个优秀子序列的价值为 $\varphi(1+\sum a_{b_i})$,求所有优秀子序列的价值和。
$1\le n\le 10^6,\ 0\le a_i\le 2\times 10^5$。

$\text{Solution:}$

有十分简单的 $\mathcal{O}(3^n)$ 做法,只需要保证在 $\text{dp}$ 的时候保证不算重即可。

由于本题价值的计算方式十分奇怪,所以第一想法应不是对价值柿子进行化简,而是考虑计算出所有 $\sum a_{b_i}$ 相等的子序列的方案数,再组合。

观察发现,如果把数字 $a$ 看做一个 $01$ 向量,那么既然子序列中值两两不交,那么其和就等价于集合取并。

令 $\text{buk}_i$ 表示 $i$ 在序列 $a$ 中出现的次数,定义其占位集合幂级数 $F(z,v)=\sum_S \text{buk}_S z^{|S|}v^S$。其中 $v$ 是一个 $01$ 向量。

如果把其乘法定义为子集卷积,那么原题中的计数等价于求这个东西的 $\exp$。根据 $\text{FMT}$ 的性质可得,当我们把 $2^n$ 种 $v$ 依次带入求点值,那么原占位集合幂计数就会变成一个只关于 $z$ 的形式幂级数。

因此直接 $\text{FMT}$ 一遍,然后对转化之后的形式幂级数暴力求 $\exp$,最后再 $\text{IFMT}$ 回来即可。

时间复杂度 $\mathcal{O}(n^22^n)$。


$\text{Summary:}$

当我们看见不太好看的代价函数的之后,第一想法往往是进行化简。但是对于类似本题中的 $\varphi$,他本身已经十分简洁,而且没有很好的推导方式。若类似这样的代价函数,且定义域并不大,就可以考虑先计算出每一种情况的方案数,最后再乘上代价。

同时,对于在集合不交的情况下,加法等于求交也是需要一定的观察才可以得到的结论。因此,若出现位运算与加减法共存的题目,一般来说很难处理,因此应该考虑将位运算转变为加减,或将加减转变为位运算(当然,一定要观察两类数字的性质,例如 [省选联考 2020 A 卷] 树 一题中,只需要 $+1$)。

接着的对集合幂计数求 $\exp$ 的操作,在本质上是运用了 $\text{FMT}$ 的性质,将占位集合幂级数转变为形式幂级数,从而利用为人熟知的方式求解。这从另一个角度揭示了 $\text{FMT}$ 的本质:将 $2^n$ 种取值带入求点值,中间操作对应点值相乘,而 $\text{IFMT}$ 类似插值插出系数,这个角度来看与 $\text{FFT}$ 十分相似。

添加新评论