建议加强数据
查看原帖
建议加强数据
937538
gmb7291234楼主2025/7/31 20:40
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,s,a[100005],t[100005],v[100005],o[100005],ha[100005],b[100005],b1[100005],ss;
const int p=1000000007;
int as(int l,int r){return (ha[r]-ha[l-1]+p)*b1[l-1]%p;}
int ku(int a,int b){
	int ans=1;
	while(b){
		if(b&1)ans=ans*a%p;
		a=a*a%p;
		b/=2;
	}
	return ans;
}
signed main(){
    b[0]=b1[0]=1;
    b[1]=131;b1[1]=ku(131,p-2);
    for(int i=2;i<=100000;i++){
        b[i]=b[i-1]*b[1]%p;
        b1[i]=b1[i-1]*b1[1]%p;
    }
    cin>>n>>m>>s;
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=m;i++)cin>>t[i];
    for(int r=1;r<=s;r++){
        memset(v,0,sizeof v);
        for(int c=1;c<=s;c++){
            int hh=0;
            for(int i=1;i<=n;i++){
                if(a[i]>=r)ha[i]=(ha[i-1]+b[i])%p;
                else ha[i]=ha[i-1];
            }
            for(int i=1;i<=m;i++){
                if(t[i]>=c)hh=(hh+b[i])%p;
            }
            for(int i=1;i<=n-m+1;i++){
                if(as(i,i+m-1)==hh)v[i]=1;
            }
        }
        for(int i=1;i<=n;i++)o[i]+=v[i];
    }
    for(int r=1;r<=s;r++){
        memset(v,0,sizeof v);
        for(int c=1;c<=s;c++){
            int hh=0;
            for(int i=1;i<=n;i++){
                if(a[i]==r)ha[i]=(ha[i-1]+b[i])%p;
                else ha[i]=ha[i-1];
            }
            for(int i=1;i<=m;i++){
                if(t[i]==c)hh=(hh+b[i])%p;
            }
            for(int i=1;i<=n-m+1;i++){
                if(as(i,i+m-1)==hh)v[i]=1;
            }
        }
        for(int i=1;i<=n;i++)o[i]+=v[i];
    }
    for(int i=1;i<=n-m+1;i++)if(o[i]==2*s)ss++;
    cout<<ss<<"\n";
    for(int i=1;i<=n-m+1;i++)if(o[i]==2*s)cout<<i<<"\n";
    return 0;
}

乱写的,能过!!!

2025/7/31 20:40
加载中...