ARC104F Visibility Sequence

发表于 更新于 分类于 ， ， 阅读次数：

题意：对于序列 ，定义其“前邻序列”为 ，其中 ，特殊地，若不存在 满足条件，则 。

现在给定序列 ，请问对于所有满足 的序列 ，共有多少个不同的“前邻序列”。答案对 取模。

。

  • 提示：
    • 先观察 ，找出 的某些必要性质。
    • 证明这性质是充分的（先不考虑 的限制，看是否对于每个满足性质的 都存在 满足 ）。
    • 检查反射，找出满足 的 的充要条件（上一步在构造 ，这一步是描述 的解集）。
    • 考虑 的限制，构造判定 “是否存在 使得 ” 的算法。
    • 根据上述判定算法设计 DP，进行计数。

Solution：

是一种下标关系，可以写成图的形式，便于观察。对于每个 连边 。若 则不连边。

每个点要么无出边，要么恰有一条向前连的出边，图为内向树森林。

可以发现， 显然是这森林的 dfs 序之一。

观察片刻，这性质应当很充分了。先不对 加上 的限制，考虑对于任意一个符合条件的 （dfs 序为 的内向树森林），是否能构造出所对应的 。

答案是肯定的。考虑赋值方案的必要条件：

  • 对于节点 ，是的儿子
  • 上一个兄弟 。

不难发现这也是充分的，而且符合条件的赋值方案必定存在。

接下来考虑 的限制，如何判定某个 能否被生成？简单起见，我们希望为 构造一个对应的“最优”的 ，使得若 不满足条件，其余方案也不满足。

观察 对 的限制，每个位置都有一个上界。我们要让 的每一位同时达到下界。这并不一定总能实现，但我们不妨试试，毕竟那些不能实现的情况往往太过复杂，不值得优先考虑。

观察前文的充要条件，一个 的约束基于其余若干 的 。当然是他们都取得下界的时候，该 也能取得下界，不难归纳证明各个位置的下界能同时取得。

接下来考虑如何计数。

由于 是这森林的 dfs 序，每个子树的 dfs 序必然是一个编号区间。设 为编号 形成一片森林的情况，其中最大权值（最后一棵树的根）为 。此处显然有 。

边界：。

枚举最后一棵树的编号区间 ，这样最大值就确定为其根 。前后两部分都是森林，设前后的 分别为 ，而 的取值是 。有转移

（特别地，规定 ，对应空树）

可以前缀和优化，复杂度 。