P5270 题解

· · 题解

P5270 solution

题目链接

P5270 无论怎样神树大人都会删库跑路

做法

首先，通过数据范围可以发现，Q 是 10^9 级别的，所以我们就想到这道题的答案可能具有一定的周期性，所以，发现串的后缀是具有周期性的，所以我们考虑先做两个周期，剩下的直接用第二个周期的规律往后推（因为第一个周期和后面的周期可能不同，因为第一个周期之前没有东西，但第二个周期之前有）。

那么，接下来问题就转化成了如何算出两个周期。

首先注意到两个序列相同仅当它们的长度相同。于是对于一次询问，我们只要查询一个后缀是否与 S 相同。

我们注意到，需要将一个后缀排序后变成 S，实际上就是要让这个后缀里所有数的出现次数都和 S 相等。

这样的“相等“的规定，这样的检查是否相同，很难不想到是哈希。考虑如何设计哈希函数。发现它与数的顺序无关，只与每个数的大小有关。

所以，我们设计序列 S 的哈希函数 f(S) 为（开 \tt ull 让它自然溢出）：

f(S)=\sum\limits_{i=1}^{|S|}{(10^9+7)^{S_i}}

若两个序列哈希值相等，则这两个序列在题目意义下是相同的。而且，这个哈希函数是有可加性的。

然后，因为在跑的过程中，不一定每段都会被完整的取到，所以，我们还要记录对于一个会被加入的序列，每个后缀的哈希函数值。这样子跑一个类似于双指针的东西，我们就可以 O(m) 求出前两轮的答案。后面的就可以以此类推了（注意：后面的是以第二轮“类推”）。总复杂度是线性的，可以跑的飞快。

code

#include <bits/stdc++.h>
#define int long long
using namespace std;
int id[100005],roundans[100005];
vector <int> arr[100005],pre[100005];
unsigned long long g,f[100005],garr[100005];
//roundans:有规律的答案
//arr:序列是什么
//pre:哈希值前缀
//garr:小字符串哈希值
//f:每个数的哈希值
//g:序列 S 的哈希值
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(); cout.tie();
    f[0]=1;
    for(int i=1;i<=100000;++i)
        f[i]=f[i-1]*1000000007;
    int n,T,Q; cin >> n >> T >> Q;
    for(int i=1;i<=T;++i) {
        int x; cin >> x; g+=f[x];
    }
    for(int i=1;i<=n;++i) {//预处理
        int length; cin >> length;
        arr[i].push_back(0);
        for(int j=1;j<=length;++j) {
            int x; cin >> x;
            arr[i].push_back(x);
            garr[i]+=f[x];
        }
        unsigned long long u=0;
        pre[i].push_back(0);
        for(int j=1;j<=length;++j) {
            u+=f[arr[i][j]];
            pre[i].push_back(u);
        }
    }
    int m; cin >> m;
    for(int i=1;i<=m;++i) cin >> id[i];
    int length=0; int l=1; int tp=0; int tans=0;
    bool gull=false;
    for(int i=1;Q;--Q,++i) {//先做几遍
        int p=(i-1)%m+1;
        length+=arr[id[p]].size()-1;
        tp+=garr[id[p]];
        while(length-arr[id[l]].size()+1>=T) {
            length-=arr[id[l]].size()-1;
            tp-=garr[id[l]];
            ++l;
            if(l>m) l=1;
        }
        if(length>=T) {
            if(gull) roundans[p]=roundans[p-1];
            if(tp-pre[id[l]][length-T]==g) {
                ++tans;
                if(gull) ++roundans[p];
            }
        }
        if(gull==true && p==m) {
            Q--;
            break;
        }
        if(length>=T && p==m) gull=true;
    }
    tans+=(Q/m)*roundans[m];//然后用规律
    tans+=roundans[Q%m];
    cout << tans;
    return 0;
}