CF213E Two Permutations 题解

Meteor_ · 2023-11-07 20:03:00 · 题解

CF213E Two Permutations 题解

题目大意

给出两个排列 a, b，长度分别为 n, m，你需要计算有多少个 x，使得 a_1 + x, a_2 + x, \dots, a_n + x 是 b 的子序列

分析

挺不错的一道题。

判断两个排列是否相同，不难想到哈希。动态维护哈希值，不难想到线段树。

题解

其实分析里已经把思路说的差不多了，就是动态维护哈希值并判断是否相等。

可以发现，x 一定不会很大，具体来说，x \in [0, m - n]。

所以我们可以枚举每一个 x，判断在排列 b 中，值域在 [x, n + x] 里的子序列构成的哈希值与 a 排列的哈希值是否相等。

主要来说说每次让 x 加一时两个排列的哈希值怎么变。

设一个排列 p 的哈希值 Hash_p = base^{n - 1} \times p_1 + base^{n - 2} \times p_2 + \dots + base^0 \times p_n。

每次 x 加一时，Hash_a 会加上 base^{n - 1} + base^{n - 2} + \dots + base^0，这个不难发现。而这个值我们可以预处理出来，每次直接加就行。