CF1175F The Number of Subpermutations 题解

Dregen_Yor · 2022-10-17 21:03:01 · 题解

更好的阅读体验。

背景

最近打模拟赛用到了异或哈希的知识，于是就在 CF 上找到了这一题。

据出题人说：“xor-hashing 可能最近普及开来了，记得 PKUSC 和 ABC 都有考过啊。”

思路

为了避免异或值重复的情况，我们用梅森旋转算法将 1\sim n 赋成一个随机值，用一个数组 base_i 记录前 i 个数的异或和，这样一会在判断该序列是否为一个自排列的时候会方便很多。

我们考虑枚举所有 1 的位置，分别向左和向右搜索能达到的最大值，用这个最大值当做序列的长度，设这个最大值为 m，并判断序列内的异或和是否与前 m 个元素的异或和相等即可。

为了节省时间复杂度，我们考虑利用前缀和进行优化，用前缀和模拟向左搜索的过程，再将整个序列倒过来模拟向右搜索的过程即可。

代码

#include<bits/stdc++.h>
#include<ctime>
#define int long long
#define N 300010
using namespace std;
int n,a[N],rd[N],pre[N],base[N],ans;
mt19937_64 rnd(time(0));
signed main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        rd[i]=rnd();
        base[i]=base[i-1]^rd[i];
    }
    for(int i=1;i<=n;i++){
        pre[i]=rd[a[i]]^pre[i-1];
    }
    for(int i=1,j=1;i<=n;i++){
        if(a[i]==1){
            j=1;
            ans++;
        }
        else {
            j=max(j,a[i]);
            if(i>=j&&(pre[i]^pre[i-j])==base[j]){
                ans++;
            }
        }
    }
    for(int j=1;n-j+1>=j;j++){
        swap(a[j],a[n-j+1]);
    }
    for(int i=1;i<=n;i++){
        pre[i]=rd[a[i]]^pre[i-1];
    }
    for(int i=1,j=1;i<=n;i++){
        if(a[i]==1){
            j=1;
        }
        else {
            j=max(j,a[i]);
            if(i>=j&&(pre[i]^pre[i-j])==base[j]){
                ans++;
            }
        }
    }
    printf("%lld",ans);
    return 0;
}