【题解】[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}$ 十分相似。