题解：P6080 [USACO05DEC] Cow Patterns G

fish_love_cat · 2026-06-04 18:06:03 · 题解

我也许是完全不会 hash？怎么被奶龙题卡了一万年。

多倍经验。

考虑哈希，考虑暴力哈希怎么做。

首先把这个串给离散化一下，然后给每个元素上一个权，权乘上 base^k 然后求和得到这个串的哈希值。

容易发现不管是否离散化，每一类元素的 base^k 的和是固定的，考虑维护这个东西。

然后我们对每个元素开桶维护出现次数，于是我们每次新增和删除元素都可以 O(s) 求出每种数离散化后的排名。

于是你发现哈希值可以 O(s) 的从上一位转移得到。

直接做就是 O(ns) 的。

#include<bits/stdc++.h>
#define int long long
#define mod 998244353
#define base 131
using namespace std;
mt19937 rnd(754021);
int qpow(int a,int b=mod-2){
    int ans=1;
    while(b){
        if(b&1)ans=ans*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return ans;
}
int rk[30];
int sm[30];
int a[100005];
int b[25005];
int bs[30];
int bas=1;
int flc;
int n,m,s;
int qry(){
    int flc=0;
    int qwq=0;
    for(int i=1;i<=s;i++)
    if(sm[i]){
        qwq++;
        flc=(flc+bs[i]*rk[qwq]%mod)%mod;
    }
    return flc;
}
signed main(){
    cin>>n>>m>>s;
    if(n<m){
        cout<<0;
        return 0;
    }
    for(int i=1;i<=s;i++)
    rk[i]=rnd();
    for(int i=1;i<=n;i++)
    cin>>a[i];
    for(int i=1;i<=m;i++)
    cin>>b[i],
    sm[b[i]]++,
    bs[b[i]]=(bs[b[i]]+bas)%mod,
    bas=bas*base%mod;
    bas=1;
    flc=qry();
    memset(sm,0,sizeof sm);
    memset(bs,0,sizeof bs);
    for(int i=1;i<=m;i++)
    sm[a[i]]++,
    bs[a[i]]=(bs[a[i]]+bas)%mod,
    bas=bas*base%mod;
    bas=bas*qpow(base)%mod;
    vector<int>ret;
    if(qry()==flc)ret.push_back(1);
    for(int i=m+1;i<=n;i++){
        sm[a[i-m]]--;
        bs[a[i-m]]+=mod-1;
        bs[a[i-m]]%=mod;
        for(int j=1;j<=s;j++)
        bs[j]=bs[j]*qpow(base)%mod;
        sm[a[i]]++;
        bs[a[i]]=(bs[a[i]]+bas)%mod;
        if(qry()==flc)ret.push_back(i-m+1);
    }
    cout<<ret.size()<<'\n';
    for(int i:ret)cout<<i<<'\n';
    return 0;
}
// 老是用外号也多有不便。
// 恐怕那位叫菈恩什么来著的学姊，也尽可能用心地赶著帮她们取了名字吧。

// 只是，来不及了。

// 该接受名字的对象，已经缺了一半。

//「然后呢，苹果真正的名字是──」

//「不。」
// 他摇头。
//「希望你别说。对我而言，今后那孩子还是一直叫苹果。」