为什么我的哈希会CE阿,gdoi普及组day2T1因为CE爆0了QAQ
  • 板块学术版
  • 楼主frank15
  • 当前回复6
  • 已保存回复6
  • 发布时间2021/4/12 21:11
  • 上次更新2023/11/5 00:37:05
查看原帖
为什么我的哈希会CE阿,gdoi普及组day2T1因为CE爆0了QAQ
362627
frank15楼主2021/4/12 21:11

我的c++和考场的c++都没报错

#include<cstdio>
#include<string>
#include<iostream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int maxn=2e5+5,base=1331;
ull t,m,a,b,c,d,e;
ull ans,tot;ull A[maxn];
ull HASH;ull hash[maxn];
ull s[maxn],mi[maxn];
ull C;
void inita(){
	  s[0]=a;
	  for(int i=1;i<t;i++)
		    s[i]=((s[i-1]<<b)+(s[i-1]>>c)+d)%e;
}
ull qpow(ull k){
	  ull res=1,B=base;
	  while(k){
		    if(k&1)
			      res*=B;
		    B*=B;
		    k>>=1;  
	}
	  return res;
}
int main(){
//  freopen("noise.in","r",stdin);
//  freopen("noise.out","w",stdout);
  scanf("%llu%llu",&t,&m);
  scanf("%llu%llu%llu%llu%llu",&a,&b,&c,&d,&e);
  inita();
  for(int i=1;i<=t;i++){
    scanf("%llu",&C);
    if(s[i-1]>C)
      s[i-1]=C+256-s[i];
    else
		s[i-1]=C-s[i-1];
      }
  for(int i=1;i<=m;i++){
    scanf("%llu",&C);
    mi[i-1]=C;
  }
  hash[0]=s[0]*qpow(t);
  for(int i=1;i<t;i++)
    hash[i]=hash[i-1]+s[i]*qpow(t-i);
  for(int i=0;i<m;i++)
    HASH=(HASH+mi[i])*base;
  for(int i=0;i+m-1<t;i++)
    if(HASH*qpow(t-(i+m-1)-1)==hash[i+m-1]-hash[i-1])
      ans++,A[++tot]=i;
  if(!ans){
    puts("wrong");
    return 0;
  }
  cout<<ans<<endl;
  for(int i=1;i<=tot;i++)
    printf("%llu",A[i]+1);
return 0;
}
2021/4/12 21:11
加载中...